记录编号 |
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);
}
}