Cod sursa(job #2837605)

Utilizator loraclorac lorac lorac Data 22 ianuarie 2022 12:19:37
Problema Mins Scor 80
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.46 kb
#include <bits/stdc++.h>
using namespace std;
ifstream in("mins.in");
ofstream out("mins.out");
typedef long long ll;
const int lim=1e6+4;
vector<int> used;
int prod[lim];
int last[lim];
bool ok[lim];
int phi[lim];
int nrb[150];
int pr[150];
int lp[lim];
int b[150];
int c,d;
ll ans;
int main()
{
    in>>c>>d; --c,--d;
    if(c>d) swap(c,d);
    for(int i=1;i<=c;++i)
        prod[i]=1;
    phi[1]=d;
    ans+=1LL*d;
    for(int i=1;i<=140;++i)
    {
        nrb[i]=__builtin_popcount(i)+1;
        for(int j=0;;++j)
        if(i&(1<<j))
        {
            b[i]=j;
            break;
        }
    }
    for(int i=2;i<=c;++i)
    {
        if(!ok[i])
        {
            for(int j=i;j<=c;j+=i)
                ok[j]=true,
                prod[j]*=i,
                last[j]=i;
        }
        if(prod[i]!=i)
        {
            ans+=1LL*phi[prod[i]];
            continue;
        }
        int aux=i;
        while(aux>1)
        {
            used.push_back(last[aux]);
            aux/=last[aux];
        }
        int nr=used.size()-1;
        phi[i]=phi[i/used[0]];
        phi[i]-=(d/used[0]);
        pr[0]=used[0];
        for(int a=1;a<(1<<nr);++a)
        {
            pr[a]=pr[(a^(1<<b[a]))]*used[b[a]+1];
            if(nrb[a]%2==1)
                phi[i]-=(d/pr[a]);
            else phi[i]+=(d/pr[a]);
        }
        ans+=1LL*phi[i];
        used.clear();
    }
    out<<ans<<'\n';
    return 0;
}