Cod sursa(job #2292481)

Utilizator Dragne.Andrei11Dragne Andrei Dragne.Andrei11 Data 29 noiembrie 2018 16:57:05
Problema Principiul includerii si excluderii Scor 70
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.89 kb
#include <bits/stdc++.h>

using namespace std;

vector <int> factori;

void descomp(long long x)
{
		for(int i=2;i*i<=x;i++)
		{
			if(x%i==0)
			{
				while(x%i==0)
					x/=i;
				factori.push_back(i);
			}
		}
		if(x>1)
			factori.push_back(x);
}
long long pinex(long long x)
{
	long long s=0;
	long long n=(1<<factori.size())-1;
	for(long long i=1;i<=n;i++)
	{
		int p=1;
		int siz=0;
		for(int j=0;j<factori.size();j++)
		{
			if((i&(1<<j))!=0)
			{
				p*=factori[j];
				siz++;
			}
		}
		if(siz%2==0)
			s-=x/p;
		else
			s+=x/p;
	}
	return s;
}

int main()
{
    freopen("pinex.in", "r", stdin);
    freopen("pinex.out", "w", stdout);
    short m;
    long long a, b;

		scanf("%hd", &m);
		while(m)
		{
				scanf("%lld%lld", &a, &b);
				descomp(b);
				printf("%lld\n", a-pinex(a));
				factori.clear();
				m--;
		}

    return 0;
}