Cod sursa(job #1952357)

Utilizator MikeComputerMihnea Andreescu MikeComputer Data 4 aprilie 2017 07:15:10
Problema Fractii Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.95 kb
#include <stdio.h>

using namespace std;

FILE*f=fopen("fractii.in","r");
FILE*g=fopen("fractii.out","w");

#define ll long long

ll n,v[1000010],t[1000010],m[1000010],s,p,i,j,e,x,y;

void ciur(){
    v[1]=1;
    ll d,i;
    for (d=2;d<=n;d++)
        if (!v[d]) {
            if (!m[d]){
                s+=2*(d-1);
                t[d]=d-1;
                m[d]=d;
            }
            for (i=2;i*d<=n;i++) {
                v[d*i]=1;
                if (!m[i*d]){
                    m[i*d]=d;
                }
            }
        }
        else{
            x=d;
            y=1;
            while (x%m[d]==0){
                x/=m[d];
                y*=m[d];
            }
            y/=m[d];
            t[d]=t[x]*y*(m[d]-1);
            s+=2*t[d];
        }
}

int main()
{
    fscanf(f,"%lld",&n);
    t[1]=1;
    s=1;
    ciur();
    fprintf(g,"%lld",s);
    fclose(f);
    fclose(g);
    return 0;
}