# Cod sursa(job #632103)

Utilizator Data 10 noiembrie 2011 12:27:24 Principiul includerii si excluderii 70 cpp done Arhiva educationala 1.35 kb
``````#include <stdio.h>
#include <math.h>
#include <algorithm>
#include <string.h>

using namespace std;

#define ll long long
#define MAX_P 1000000

ll M, A, B, fact[30];
int fprim[80000];
bool prim[MAX_P];

void prec() {
//precalculez numerele prime mai mici ca sqrt(B)

fill(prim + 2, prim + MAX_P, 1);

for (int i = 2; i < MAX_P; i++)
if (prim[i]) {
for (int j = 2 * i; j < MAX_P; j += i)
prim[j] = false;
fprim[++fprim[0]] = i;
}
}

void solve() {
ll t = 0, d = 0;
while (B > 1) {
d++;
if (B % fprim[d] == 0) {
fact[++t] = fprim[d];
while (B % fprim[d] == 0)
B /= fprim[d];
}

if (fprim[d] > sqrt(B) && B > 1) {
fact[++t] = B;
B = 1;
}
}

ll sol = A;
for (int i = 1; i < (1 << t); i++) {
ll nr = 0, prod = 1;
for (int j = 0; j < t; j++)
if ((1 << j) & i) {
prod = 1LL * prod * fact[j + 1];
nr++;
}

if (nr % 2) nr = -1;
else nr = 1;

sol = sol + 1LL * nr * A / prod;
}

printf("%lld\n", sol);
}

int main() {

freopen("pinex.in", "r", stdin);
freopen("pinex.out", "w", stdout);

prec();

scanf("%lld", &M);
for (int i = 1; i <= M; i++) {
scanf("%lld %lld", &A, &B);
solve();
}

return 0;
}

``````