Pagini recente » Istoria paginii utilizator/zamfi | Borderou de evaluare (job #241595) | Cod sursa (job #2456025) | Profil adrianxer | Cod sursa (job #2612484)
#include <fstream>
#include <vector>
#include <bitset>
using namespace std;
using LL = long long;
const LL MAX_SIZE = 1E6;
LL res;
bitset<MAX_SIZE + 1> prime;
vector<LL> prime_arr;
void precalc_prime_arr()
{
prime[0] = prime[1] = 1;
for (LL i = 2; i * i <= MAX_SIZE; i += 1 + i != 2)
{
if (prime[i] == 0)
{
for (LL j = i; j <= MAX_SIZE / i; ++j)
{
prime[j * i] = 1;
}
prime_arr.emplace_back(i);
}
}
}
void solve(LL A, LL B)
{
vector<LL> prime_facs;
prime_facs.reserve(20);
int index = 0;
for (; prime_arr[index] * prime_arr[index] <= B; ++index)
{
if (B % prime_arr[index] == 0)
{
prime_facs.emplace_back(prime_arr[index]);
while (B % prime_arr[index] == 0)
{
B /= prime_arr[index];
}
}
}
if (B > 1)
{
prime_facs.emplace_back(B);
}
LL nr_subsets = 0, cur_product = 1;
for (LL i = 1; i < (1LL << prime_facs.size()); ++i)
{
for (LL j = 0; j < prime_facs.size(); ++j)
{
if ((1LL << j) & i)
{
cur_product *= prime_facs[j];
++nr_subsets;
}
}
LL sign;
if (nr_subsets % 2 == 0)
{
sign = -1;
}
else
{
sign = 1;
}
res += sign * A / cur_product;
cur_product = 1;
nr_subsets = 0;
}
}
int main()
{
precalc_prime_arr();
ifstream fin("pinex.in");
LL M;
fin >> M;
ofstream fout("pinex.out");
while (M--)
{
LL A, B;
fin >> A >> B;
solve(A, B);
fout << A - res << "\n";
res = 0;
}
}