Cod sursa(job #2418836)

Utilizator dragos231456Neghina Dragos dragos231456 Data 6 mai 2019 16:29:28
Problema Principiul includerii si excluderii Scor 30
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.36 kb
#include <bits/stdc++.h>
#define pb push_back

using namespace std;

typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int,int> per;
typedef long double LD;


const int N=1000005;
const int M=1005;
const LL mod=1000000007;
const int inf=(1<<30);
const LL linf=(1LL<<61);

ifstream f("pinex.in");
ofstream g("pinex.out");

int m,nr,l,s,t,lim;
bool ciur[N];
LL a,b,prime[N],fact[M],sub[M],rez;

void submultime(int x)
{
    t=1LL;
    for(int i=1;i<=l;++i)
    {
        if(x%2) sub[i]=1, ++nr, t*=fact[i];
        else sub[i]=0;
        x/=2;
    }
}

LL baga()
{
    if(nr%2) return (a/t);
    else return (-a/t);
}

void Eratosthenes()
{
    ciur[1]=1;
    int H=N-5;
    for(int i=2;i<=H;++i)
    {
        if(!ciur[i])
        {
            prime[++s]=i;
            for(int j=2;i*j<=H;++j) ciur[i*j]=1;
        }
    }
}

int main()
{
    f>>m; ++m;
    Eratosthenes();
    while(--m)
    {
        f>>a>>b;
        t=sqrt(b); l=0LL;
        for(int i=1;i<=s && b!=1;++i) if(b%prime[i]==0)
        {
            fact[++l]=prime[i];
            while(b%prime[i]==0) b/=prime[i];
        }
        lim=(1<<l)-1; rez=0LL;
        for(int i=1;i<=lim;++i)
        {
            nr=0;
            submultime(i);
            rez+=baga();
        }
        g<<(a-rez)<<'\n';
    }
    return 0;
}