Cod sursa(job #1917522)

Utilizator FlorinHajaFlorin Gabriel Haja FlorinHaja Data 9 martie 2017 12:26:56
Problema Principiul includerii si excluderii Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.24 kb
#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;
}