记录编号	540757	评测结果	AAAAAAAAAA
题目名称	最大公约数	最终得分	100
用户昵称	神利·代目	是否通过	通过
代码语言	C++	运行时间	0.090 s
提交时间	2019-08-28 21:25:38	内存使用	4.40 MiB

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include <algorithm>
#define ll long long
#define times 2

ll gcd(ll a, ll b) {
	return b == 0 ? a : gcd(b, a % b);
}

//O(1)快速乘法
ll multi(ll a, ll b, ll c) {
	return a * b % c;
}
ll mypow(ll x, ll y, ll mod) {
	ll res = 1;
	while (y) {
		if (y & 1)res = multi(res, x, mod);
		y >>= 1;
		x = multi(x, x, mod);
	}
	return res;
}
//miller-rabin素数测试，可以判断long long范围内的数是否是素数，该模板已经通过了HDU6608和COGS2489的测试（times=5时）
//如果选用这11个数，那么那么10^16内没有出错的数
//int pp[11] = {2, 3, 5, 7, 11, 13, 17, 19, 23, 61, 24251};
//如果选用2, 3, 7, 61和24251作为底数，那么10^16内唯一出错的数为46856248255981
int pp[5] = { 2, 3, 7, 61, 24251 };
bool miller_rabin(ll n) {
	if (n < 2)return 0;//负数,0,1都不是质数
	if (n == 2 || n == 3 || n == 5 || n == 7 || n == 11)
		return 1;
	if (!(n & 1) || !(n % 3) || !(n % 5) || !(n % 7) || !(n % 11))
		return 0;
	ll s = 0, t = n - 1;
	while (!(t & 1)) {
		++s;
		t >>= 1;
	}
	for (int i = 0; i < times && pp[i] < n; ++i) {
		ll a = pp[i];
		ll b = mypow(a, t, n);
		for (int j = 0; j < s; ++j) {
			ll k = multi(b, b, n);
			if (k == 1 && b != 1 && b != n - 1)
				return 0;
			b = k;
		}
		if (b != 1)return 0;
	}
	return 1;
}

//大整数质因数分解，支持long long范围内的整数
ll rho(ll n, ll c) {
	ll k = 2, x = rand() % n, y = x, p = 1;
	for (ll i = 1; p == 1; ++i) {
		x = multi(x, x, n) + c;
		if (x >= n)x -= n;
		p = y > x ? y - x : x - y;
		p = gcd(n, p);
		if (i == k)
			y = x, k += k;
	}
	return p;
}
ll p[110];
void solve(ll n) {
	if (miller_rabin(n)) {
		p[++p[0]] = n;
		return;
	}
	ll t = n;
	while (t == n)t = rho(n, rand() % (n - 1) + 1);//注意：t一定不为1
	solve(t);
	solve(n / t);
}

ll n, m, ans, a[110], b[110];
void dfs(int pos, ll now, ll phi) {
	if (pos > a[0]) {
		if(n / now >= m)
			ans += phi;
		return;
	}
	dfs(pos + 1, now, phi);
	phi *= a[pos] - 1;
	now *= a[pos];
	for (int i = 1; i <= b[pos]; ++i) {
		dfs(pos + 1, now, phi);
		phi *= a[pos];
		now *= a[pos];
	}
}


int main() {
	freopen("gcd.in", "r", stdin);
	freopen("gcd.out", "w", stdout);
	int T; scanf("%d", &T);
	while (T--) {
		p[0] = a[0] = ans = 0;
		scanf("%lld%lld", &n, &m);
		if(n!=1)solve(n);
		std::sort(p + 1, p + p[0] + 1);
		for (int i = 1; i <= p[0]; ++i) {
			if (i == 1 || p[i] != p[i - 1]) {
				a[++a[0]] = p[i];
				b[a[0]] = 0;
			}
			++b[a[0]];
		}
		dfs(1, 1, 1);
		printf("%lld\n", ans);
	}

}