SPOJ:Divisors of factorial (hard) (唯一分解&优化)

发布时间：2020-12-14 04:50:05 所属栏目：大数据来源：网络整理

导读：Factorial numbers are getting big very soon,you‘ll have to compute the number of divisors of such highly composite numbers. Input The first line contains an integer? T ,the number of test cases. On the next? T ?lines,you will be given two

Factorial numbers are getting big very soon,you‘ll have to compute the number of divisors of such highly composite numbers.

Input

The first line contains an integer?T,the number of test cases.
On the next?T?lines,you will be given two integers?N?and?M.

Output

Output?T?lines,one for each test case,with the number of divisors of the factorial of?N.
Since the answer can get very big,output it modulo?M.

Example

Input:
3
2 1000
3 11
4 5
Output:
2
4
3

Constraints

0 < T < 5432
1 < N < 10^8
1 < M < 10^9

For N,M : uniform random input in the range.
One input file.

题意: ?T组数据给定N,M ; 求N的阶乘的因子个数,结果模M .

思路: ? 对于求某个数的因子个数,我们知道是唯一分解为素数,表示为素数的幂的乘积形式a1^p1*a2^p2... 然后结果就是所有(p1+1)*(p2+1)...的乘积.

? ? ? ? ?但是这里的N的阶乘过大,?而且多组询问,T也过大,而且需要模不同的M (即可能不能离线求).?

? ? ? ? 考虑到对于大于10000的素数 ?最多除一次所以单独考虑即把前面1229个素数和后面第1230个素数到最后一个素数分开考虑 ?:前面的暴力除,复杂度1229*logN

? ? ? ? 后面部分分块把除数相同的合并. 然后快速幂,复杂度logN*logN

所以最后的复杂度是O(T*1330*logN)

#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
const int maxn=1e8;
const int Mod=1e9+7;
int p[6000000],vis[maxn+10],cnt;
void prime()
{
    for(int i=2;i<=maxn;i++){
        if(!vis[i]) p[++cnt]=i;
        for(int j=1;j<=cnt&&(ll)i*p[j]<=maxn;j++){
            vis[i*p[j]]=1;
            if(!(i%p[j])) break;
        }
    }
}
int qpow(int a,int x,int M){
    int res=1;
    while(x){
        if(x&1) res=(ll)res*a%M;
        a=(ll)a*a%M; x>>=1;
    } return res;
}
int main()
{
    int T,i,j,x,M,pos,ans;
    prime();  scanf("%d",&T);
    for(i=1;i<=T;i++){
        ans=1; scanf("%d%d",&x,&M);
        for(j=1;j<1230&&p[j]<=x;j++){  //暴力部分 
            int tmp=x,num=0; 
            while(tmp){
                num+=tmp/p[j]; tmp/=p[j];
            }
            ans=(ll)ans*(num+1)%M;
        }
        pos=upper_bound(p+1,p+cnt+1,x)-p; pos--;
        int fcy;
        for(j=1230;j<=pos;j=fcy+1){        //合并部分 
            fcy=upper_bound(p+1,x/(x/p[j]))-p; fcy--;
            if(fcy>pos) fcy=pos;
            ans=(ll)ans*qpow(x/p[j]+1,fcy-j+1,M)%M;
        }
        printf("%dn",ans);
    }
    return 0;
}

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!

SPOJ:Divisors of factorial (hard) (唯一分解&amp;优化)

Input

Output

Example

Constraints

SPOJ:Divisors of factorial (hard) (唯一分解&优化)