Pagini recente » Cod sursa (job #3171327) | Cod sursa (job #1556457) | Cod sursa (job #1551955) | Cod sursa (job #234551) | Cod sursa (job #1917522)
#include <fstream>
#include <iostream>
using namespace std;
ifstream f("pinex.in");
ofstream g("pinex.out");
const int MAX = 1000001;
bool prim[MAX];
int np[100005], vv, n;
int vp[100005];
long long a, b;
void ciur() {
int i, j;
np[vv = 1]=2;
for (i = 3; i <= MAX; i += 2)
if (prim[i] == 0) {
np[++vv] = i;
for (j = i+i; j <= MAX; j += i)
prim[j] = 1;
}
}
long long query() {
int i, j, t = 0;
long long prod = 1;
for (i = 1; b > 1; i++) {
if (b%np[i]==0) {
while (b%np[i] == 0)
b /= np[i];
vp[t++] = np[i];
}
if (1LL*np[i]*np[i] > b && b > 1) {
vp[t++] = b;
b = 1;
}
}
long long sol = a;
int nr = 0;
for (i = 1; i < (1<<t); i++) {
prod = 1;
nr = 0;
for (j = 0; j < t; j++)
if ((i&(1<<j)))
prod = 1LL*prod*vp[j], nr++;
if (nr%2 == 0) nr = 1;
else nr = -1;
sol += 1LL*nr*(a/prod);
}
return sol;
}
int main() {
ciur();
f >> n;
while (n--) {
f >> a >> b;
g << query() << '\n';
}
return 0;
}