HDU2582(素数筛)

xiaoxiao2021-02-28  83

还是整理公式遇到的水题。 公式:若 G(n)=gcd(C1n,C2n...Cn1n) ,那么G(n)为 (1)n为素数,答案为n (2)n有多个素数因子,答案为1 (3)n有一个素因子,答案为该素因子; 那么这个题就很简单了,除了素数和由一个素数相乘的其他的都加1 直接code:

#include<stdio.h> #include<string.h> #include<math.h> #include<algorithm> #include<iostream> #include<string> #include <set> //a&3==a%4 using namespace std; #define ll long long #define mem(a) memset(a,0,sizeof(a)) const double eps=1e-8; const int maxn=1000010;//须填写 const int inf=0x3f3f3f3f; bool notprime[maxn]; int one[maxn]; ll f[maxn]; void judge() { memset(notprime,false,sizeof(notprime)); memset(one,0,sizeof(one)); notprime[0]=notprime[1]=true; for(int i=2;i<maxn;i++) { if(!notprime[i]) { if(i>maxn/i) continue; for(int j=i*i;j<maxn;j+=i) notprime[j]=true; for(int j=i*i;j<maxn;j*=i) one[j]=i; } } } void qiuf() { memset(f,0,sizeof(f)); f[2]=0; for(int i=3;i<maxn;i++) { if(!notprime[i]) f[i]=f[i-1]+(ll)(i); else if(one[i]!=0) f[i]=f[i-1]+(ll)(one[i]); else f[i]=f[i-1]+1ll; } } int main() { judge(); qiuf(); int n; while(scanf("%d",&n)!=EOF) { printf("%lld\n",f[n]); } return 0; }
转载请注明原文地址: https://www.6miu.com/read-56273.html

最新回复(0)