Cod sursa(job #2167475)

Utilizator stefdascalescuStefan Dascalescu stefdascalescu Data 13 martie 2018 21:53:35
Problema Mins Scor 65
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.18 kb
#include<bits/stdc++.h>
using namespace std;
ifstream f("mins.in");
ofstream g("mins.out");
bool pr[1000002];
int prime[80002],nr;
int a,b;
vector<int>v;
void ciur()
{
    for(int i=2;i<=1000000;++i)
        if(!pr[i])
        {
            prime[++nr]=i;
            for(int j=i+i;j<=1000000;j+=i)
                pr[j]=1;
        }
}
int curr;
int main()
{
    ciur();
    f>>a>>b;
    --a;
    --b;
    long long ss=1LL*a*b;
    if(a>b)
        swap(a,b);
    for(int i=2;i<=a;++i)
    {
        curr=i;
        int nr=i;
        v.clear();
        for(int j=1;prime[j]*prime[j]<=nr;++j)
            if(nr%prime[j]==0)
            {
                v.push_back(prime[j]);
                while(nr%prime[j]==0)
                    nr/=prime[j];
            }
        if(nr>1)
            v.push_back(nr);
        for(int i=1;i<(1<<v.size());++i)
        {
            int pr=1;
            int nrb=0;
            for(int j=v.size()-1;j>=0;--j)
                if(i&(1<<j))
                    pr*=v[j],++nrb;
            if(nrb&1)
                ss-=b/pr;
            else
                ss+=b/pr;
        }
    }
    g<<ss<<'\n';
    return 0;
}