Cod sursa(job #2167510)

Utilizator stefdascalescuStefan Dascalescu stefdascalescu Data 13 martie 2018 22:03:06
Problema Mins Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.92 kb
#include<bits/stdc++.h>
using namespace std;
ifstream f("mins.in");
ofstream g("mins.out");
bool pr[1000002];
int a,b,val;
struct arr
{
    int v[8];
};
arr vv[1000002];
void ciur()
{
    int maxx=0;
    for(int i=2;i<=1000000;++i)
        if(!pr[i])
            for(int j=i;j<=1000000;j+=i)
            {
                pr[j]=1;
                vv[j].v[0]++;
                val=vv[j].v[0];
                vv[j].v[val]=i;
            }
}
int main()
{
    ciur();
    f>>a>>b;
    --a;
    --b;
    long long ss=1LL*a*b;
    for(int R=2;R<=a;++R)
        for(int i=1;i<(1<<vv[R].v[0]);++i)
        {
            int pr=1;
            int nrb=0;
            for(int j=vv[R].v[0]-1;j>=0;--j)
                if(i&(1<<j))
                    pr*=vv[R].v[j+1],++nrb;
            if(nrb&1)
                ss-=b/pr;
            else
                ss+=b/pr;
        }
    g<<ss<<'\n';
    return 0;
}