TIOJ 1514 Problem D. 橫掃射擊場

poao899    7816K    968MS    G++     0.67K     2009-11-10 16:13:38                               .

說來慚愧是亂co的(汗

唔就是求互質個數

n(1-1/p1)(1-1/p2)...(1-1/pk)

化簡

不過沒化簡完成XD


//**********************************

//1514

#include<stdio.h>
#define MAX 1000003
unsigned long long PHI[MAX],n;
int getint(){
    int g=0,c=getchar();
    while(c==10||c==32||c==9)c=getchar();
    if(c=='-')return -1;
    while(c>='0'&&c<='9'){
        g=g*10+c-48;
        c=getchar();
    }
    return g;
}
main(){
    unsigned long long *phi=PHI;
    for(int i=1;i<MAX;i+=2){
        if(i==1)i++;
        if(phi[i]==0){
            long long j=(long long)i;
            for(;j<MAX;j+=i){
                if(!phi[j])
                    phi[j]=j;
                phi[j]=phi[j]/i*(i-1);
            }
            phi[i]=i-1;
        }
       
        if(i==2)i--;
    }
    for(int i=1;i<MAX;i++){
        //if(i<20)printf("%d %I64d\n",i,phi[i]);
        phi[i]+=phi[i-1];
    }
    while(~(n=getint()))
        n?printf("%I64u\n",phi[n]*2+3):puts("0");
}