题目
有这样一个有关最大公约数的函数:
函数 f(x, y):
{
c=0
当 y>0:
{
c +=1
t = x % y
x = y
y = t
}
返回 c * x * x
}
给出三个正整数n,m,p，你需要计算:
(sum_{i=1}^{n}sum_{j=1}^{m} lfloor frac{i*j}{f(i,j)} floor)
输入格式
包含多组测试数据。
第一行有一个正整数，表示数据的组数。
接下来每行表示一组数据，这一行有三个空格隔开的正整数(n,m,p)。
保证 (n <= 666,666,666, m <= 666, p <= 666,666,666)。
最终的测试数据中共有66组数据，并且每一个(n,m,p)都是在上述范围内均匀随机生成的。
输出格式
对于每个输入数据输出一行，这一行只包含一个整数即答案。
输入样例
3
10 5 23333
100 10 23333
1000 20 23333
输出样例
271
22359
10998
题解
根据(f)的定义可得, (f(i,j)=t cdot gcd(i,j)^2), 其中(t)为辗转相除的次数
可得 $$f(i+k∗j,j)=f(j,(i+k*j)%j)=f(j,i%j)$$$$f(i,j)=f(j,i%j)$$$$(1<=t<=n)$$
然后写出几个找一下规律, 对于同一个(j), 发现类似等差数列, 首项是(i cdot j/f(i,j)), 公差为 (j cdot j/f(i,j)), 并且循环(t)次
所以先计算出首项, 再算出每一项即可
代码
#include <cstdio>
long long f(int x, int y, int &gcd, int &c) {
c = 0;
int t;
while (y) c++, t = x % y, x = y, y = t;
gcd = x;
return x * x * c;
}
long long n, m, p;
int main() {
int T;
scanf("%d", &T);
while (T--) {
scanf("%lld%lld%lld", &n, &m, &p);
int ans = 0, g, c;
long long tmp, first, d, num;
for (int j = 1; j <= m; j++) {
for (int i = 0; i < j && i <= n; i++) {
tmp = f(i, j, g, c);
d = c * j * j / tmp;
for (int k = 0; k < c; k++) {
if (i + k * j > n) break;
first = (i + k * j) * j / tmp;
num = (n - (i + k * j)) / (c * j) + 1;
ans = (ans + first * num % p + num * (num - 1) / 2 % p * d % p) % p;
}
}
}
printf("%d
", ans);
}
return 0;
}