Cod sursa(job #2698965)

Utilizator NeacsuMihaiNeacsu Mihai NeacsuMihai Data 23 ianuarie 2021 12:34:10
Problema Principiul includerii si excluderii Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.35 kb
#include <iostream>
#include <fstream>
#define NMAX 1000000
using namespace std;

ifstream fin ("pinex.in");
ofstream fout ("pinex.out");


bool pr[NMAX+1]; //= radical din 10^12
//caut numerele prime pana la radical din b
int prim[79000];
long long v[79000];

int main()
{
    int teste;
    int i, j, totalprim=0;
    long long a, b, ct, n, nrc, p, rez;
    //ciurul lui Eratostene
    for(i=4; i<=NMAX; i+=2) pr[i]=1;
    for(i=3; i*i<=NMAX; i+=2) if(pr[i]==0)for(j=i*i; j<=NMAX; j+=i) pr[j]=1;
    for(i=2; i<=NMAX; i++)
    {
        if(pr[i]==0)
        {
            prim[++totalprim]=i;
        }

    }
    //cout<<totalprim<<"\n";


    fin>>teste;
    while(teste--)
    {
        fin>>a>>b;
        rez=a;
        ct=1;
        n=0;
        while(b>1&&prim[ct]*prim[ct]<=b)
        {
            if(b%prim[ct]==0) v[++n]=prim[ct];
            while(b%prim[ct]==0) b=b/prim[ct];
            ct++;
        }
        if(b>1) v[++n]=b;

        for(i=1; i<(1<<n); i++)
        {
            nrc=0; p=1;
            for(j=0; j<n; j++)
            {
                if(i&(1<<j))
                {
                    nrc++;
                    p=p*v[j+1];
                }
            }
            if(nrc%2==1) rez=rez-a/p;
            else rez=rez+a/p;
        }
        fout<<rez<<"\n";
    }
    return 0;
}