Cod sursa(job #1983213)

Utilizator georgerapeanuRapeanu George georgerapeanu Data 21 mai 2017 14:57:33
Problema Mins Scor 50
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.71 kb
#include <iostream>
#include <bitset>
#include <cstdio>
using namespace std;
int C,D;
int nrfac[1000005];
int pr[1000005];
bitset<1000005> naj;
long long rez;
int main()
{
    freopen("mins.in","r",stdin);
    freopen("mins.out","w",stdout);
    cin>>C>>D;
    C--;///caz i = 4 de ex
    D--;
    pr[1]=D;
    rez=D;
    for(int i=2;i<=C;i++)
    {
        bool prim=(nrfac[i]==0);
        pr[i]+=D;
        for(int j=i;j<=C;j+=i)
        {
            nrfac[j]+=prim;
        }
        for(int j=i*i;j<=C;j+=i*i)
            naj[j]=1;
        for(int j=i;j<=C&&!naj[i];j+=i)
            pr[j]=pr[j]+(nrfac[i]%2==1 ? -1:1)*(D/i);
        rez+=pr[i];
    }
    cout<<rez;
    return 0;
}