Cod sursa(job #1520342)

Utilizator robx12lnLinca Robert robx12ln Data 8 noiembrie 2015 17:04:42
Problema Fractii Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.01 kb
#include<fstream>
using namespace std;
ifstream fin("fractii.in");
ofstream fout("fractii.out");
unsigned long long sol;
int n,p[40005];
char w[1000005];
void ciur(){
    w[0]=w[1]=1;
    for(int i=2;i<=n;i++){
        if(w[i]==0){
            p[++p[0]]=i;
            for(int j=i+i;j<=n;j+=i){
                w[j]=1;
            }
        }
    }
    return ;
}
unsigned long long euler(int x){
    if(x==1){
        return 1;
    }else{
        unsigned long long rez=1;
        for(int i=1;i<=p[0];i++){
            if( x % p[i] == 0 ){
                unsigned long long P = 1;
                while( x % p[i] == 0 ){
                    P *= p[i];
                    x /= p[i];
                }
                P/=p[i];
                rez = rez * ( p[i] - 1 ) * P;
                if(x==1) break;
            }
        }
        return 2 * rez;
    }
}
int main(){
    fin>>n;
    ciur();
    for(int i=1;i<=n;i++){
        sol+=euler(i);
    }
    fout<<sol<<"\n";
    return 0;
}