Cod sursa(job #2238524)

Utilizator sorgeTrifescu Stefan-Octavian sorge Data 6 septembrie 2018 11:29:25
Problema Fractii Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.14 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <cmath>
using namespace std;

ifstream in("fractii.in");
ofstream out("fractii.out");

struct triplet{
    int divizor,rezultat,putere;
};
vector<triplet> descompunereFactoriPrimi(int n){

    vector<triplet> desc;
    int d=2;
    while(n>1){
        int contor=0;
        int rez=1;
        while(n%d==0){
            contor++;
            rez*=d;
            n/=d;
        }

        if(contor>0){
            triplet tr;
            tr.divizor=d;
            tr.putere=contor;
            tr.rezultat=rez/d;

            desc.push_back(tr);
        }
        if(d==2)
            d++;
        else d+=2;
    }
    return desc;
}
int formulaForOne(int n){
    vector<triplet>desc;
    int result=1;
    desc=descompunereFactoriPrimi(n);

    for(int i=0;i<desc.size();++i)
        result*=(desc[i].divizor-1)*desc[i].rezultat;

    return result;
}

int result(int n){
    int s=0;
    for(int i=2;i<=n;++i){
        s+=formulaForOne(i)*2;

    }
    return s+1;
}
int main()
{
    int n;
    in>>n;
    out<<result(n);
    return 0;
}