Cod sursa(job #2863912)

Utilizator e_ggIonescu Dorian e_gg Data 7 martie 2022 13:37:21
Problema Mins Scor 5
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.9 kb
#include<iostream>
#include<fstream>
#include<vector>
using namespace std;
ifstream f("mins.in");
ofstream g("mins.out");
const int nmax = 1e6 + 7;
int lp[nmax],phi[nmax];
vector<int> pr;
void calc_sieve(){
    phi[1]=1;
    for(int i=2;i<=nmax;i++){
        if(lp[i]==0){
            lp[i]=i;
            phi[i]=i-1;
            pr.push_back(i);
        }
        else{
            if(lp[i]==lp[i/lp[i]])
                phi[i]=phi[i/lp[i]]*lp[i];
            else
                phi[i]=phi[i/lp[i]]*(lp[i]-1);
        }
        for(int j=0;j<(int)pr.size()&&pr[j]<=lp[i]&&i*pr[j]<=nmax;j++)
            lp[i*pr[j]]=pr[j];
    }
}
int main()
{
    calc_sieve();
    int c,d,sm;
    f>>c>>d;
    c--;
    d--;
    sm=0;
    for(int i=1;i<=c;i++)
        sm+=phi[i];
    for(int i=1;i<=d;i++)
        sm+=phi[i];
    g<<sm-1<<'\n';
    f.close();
    g.close();
    return 0;
}