Cod sursa(job #3246493)

Utilizator vladsoartavlad sofronea vladsoarta Data 3 octombrie 2024 14:17:40
Problema Mins Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.03 kb
#include <fstream>
#include <vector>
using namespace std;
ifstream cin("mins.in");
ofstream cout("mins.out");

int primiciurpoz[1000001][7];
char lgciur[1000001];
int c,d,i;
long long rsp;

long long pinex(int lim,int elem)
{
    long long ans = 0;
    for(int mask = 1; mask<(1<<lgciur[elem]); mask++)
    {
        long long p=1,nr=0;
        for(int j=0; j<lgciur[elem]; j++)
            if(mask&(1<<j))
                p = 1ll*p*primiciurpoz[elem][j],nr++;
        if(nr%2==0)
            ans-=lim/p;
        else
            ans+=lim/p;
    }
    return lim-ans;
}

int main()
{
    cin>>c>>d;
    c--,d--;
    if(c>d)
        swap(c,d);
    for(i=1;i<=d;i++)
        lgciur[i] = 0;

    for(i=2; i<=d; i++)
    {
        if(lgciur[i] == 0)
        {
            primiciurpoz[i][lgciur[i]++] = i;
            for(int j=i*2; j<=d; j+=i)
                primiciurpoz[j][lgciur[j]++] = i;
        }
    }

    for(i=1; i<=c; i++)
    {
        rsp+=pinex(d,i);
    }

    cout<<rsp;
    return 0;
}