1 条题解

  • 0
    #include<stdio.h>
    #define MAX 100000000
    #define MAXZ 6000000
    #define mod 100000007
    using namespace std;
    char v[MAX>>2];
    int prime[MAXZ],f[MAXZ];
    signed main(){
    	register int n;
    	register long long ans=1;
    	scanf("%d",&n);
    	register int m=0;
    	for(register int i=2;i<=n;i++){
    		if(!(v[i>>3]&1<<(i^((i>>3)<<3)))){ 
    			ans=ans*i,prime[++m]=i,f[m]=i;
    			if(ans>mod)ans=ans%mod;
    		} 
    		for(register int j=1;j<=m&&prime[j]*i<=n;j++){
    			int k=prime[j]*i;
    			v[k>>3]+=1<<(k^((k>>3)<<3));
    			if(!(i%prime[j])){
    				if(i==f[j]){
    					f[j]=f[j]*prime[j],ans=ans*prime[j];
    					if(ans>mod)ans=ans%mod;
    				}
    				break;
    			}
    		}
    	}
    	printf("%lld",ans);
    }

    信息

    ID
    8653
    时间
    1000ms
    内存
    125MiB
    难度
    5
    标签
    递交数
    10
    已通过
    3
    上传者