4 条题解

  • 0
    @ 2026-5-26 10:23:45
    #include<bits/stdc++.h>
    using namespace std;
    int n;
    int prime[1000006],pct;
    bitset<1000006> not_prime;
    void euler(){
    	for(int i=2;i<=n;i++){
    		if(!not_prime[i]){
    			prime[++pct]=i;
    		}
    		for(int j=1;j<=pct&&prime[j]*i<=n;j++){
    			not_prime[i*prime[j]]=1;
    			if(!(i%prime[j])) break;
    		}
    	}
    }
    const int P=1e9+7;
    long long ans=1;
    void find(){
    	for(int j=1;j<=pct;j++){
    		long long p=prime[j],ct=0;
    		while(p<=n){
    			ct+=n/p;p=p*prime[j];
    		}ans=ans*(ct*2+1)%P;
    	}
    }
    int main()
    {
    	scanf("%d",&n);
    	euler();
    	find();
    	printf("%lld",ans);
    	return 0;
    }
    /*
    1/x + 1/y = 1/n!
    1/y = 1/n! - 1/x 
    y = xn! / (x-n!)
    若要让y为正整数,
    需要:
    xn!和x-n!正整数 
    x-n! | xn!
    设x-n! = k
    则k|(k+n!)n!=kn!+n!*n!
    因为k|kn!所以上式-> k|n!*n!
    
    
    怎么求n!*n!的因数个数呢? 
    
    我们发现n!是由质数组成的
    (这里先求n!的因数个数 
    只需要找到质数p在1~n中作为因数出现了多少次
    (设为ct[p]次吧 
    cnt=连乘(ct[p_i]+1) //可以选p^0 ~ p^ct
    那么对于n!*n!,只需让ct[p]*2即可 
    
    好的,那怎么找ct呢
    在1~n中,ct[p] = n/p + n/p^2 +... 
    (n/p记录了第一个p,n/p^2记录了第二个p...... 
    
    OK*/
    

    信息

    ID
    208
    时间
    1000ms
    内存
    256MiB
    难度
    4
    标签
    (无)
    递交数
    25
    已通过
    15
    上传者