Cod sursa(job #1346355)

Utilizator EhtRalpmetFMI Ardei Claudiu-Alexandru EhtRalpmet Data 18 februarie 2015 10:38:55
Problema Fractii Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.85 kb
//#include <iostream>
#include <fstream>
#include<vector>


using namespace std;
ifstream cin("fractii.in");
ofstream cout("fractii.out");

int n,i,j;
int b[1000000],s=1;
vector<pair<int,int> > v[1000000];


int main(){
    cin>>n;

    for(i=2;i<=n;i++){
        if(v[i].size()>0){
            continue;
        }
        for(j=i;j<=n;j+=i){
            int x=j,nr=0;
            while(x%i==0){
                nr++;
                x/=i;
            }
            v[j].push_back(make_pair(i,nr));
        }
    }

    for(i=2;i<=n;i++){
        int nr=1;
        for(j=0;j<v[i].size();j++){
            int a=v[i][j].first;
            int b=v[i][j].second;
            while(b>1){
                nr*=a;
                b--;
            }
            nr*=(a-1);
        }
        s+=2*nr;
    }
    cout<<s;
    return 0;
}