HDU-5970 最大公约数

题意

给一个函数

int f(int x,int y){
	int c=0;
    while(y>0){
		c++;
        t=x%y;
        x=y;
        y=t;
    }
    return c*x*x;
}

给出n,m,p，求$\Large\sum\limits_{i=1}^n\sum\limits_{j=1}^m\lfloor\frac {i*j} {f(i,j)}\rfloor$

题解

$$ans=\sum\limits_{j=1}^m\sum\limits_{i=1}^j\sum\limits_{k=0}^{i+j*k\le n}\lfloor\frac {j*(i+j*k)} {c*x*x}\rfloor\\=\sum\limits_{j=1}^m\sum\limits_{i=1}^j\sum\limits_{k=0}^{c-1}\sum\limits_{p=0}^{i+j*(k+p*c)\le n}\lfloor\frac {j*(i+j*(k+p*c))} {c*x*x}\rfloor\\ =\sum\limits_{j=1}^m\sum\limits_{i=1}^j\sum\limits_{k=0}^{c-1}\sum\limits_{p=0}^{i+j*(k+p*c)\le n}\lfloor\frac {j*(i+j*k)} {c*x*x}\rfloor+\frac {p*j*j} {x*x}$$

代码

#include <bits/stdc++.h>
#define forl(i, l, r) for (int i = l; i <= r; i++)
#define forr(i, r, l) for (int i = r; i >= l; i--)
#define for1(i, n) for (int i = 1; i <= n; i++)
#define for0(i, n) for (int i = 0; i < n; i++)
#define meminf(a) memset(a, inf, sizeof(a))
#define mem_1(a) memset(a, -1, sizeof(a))
#define mem0(a) memset(a, 0, sizeof(a))
#define inlld(lld) scanf("%lld", &lld)
typedef unsigned long long ull;
#define inlf(f) scanf("%lf", &f)
#define ind(d) scanf("%d", &d)
#define ins(s) scanf("%s", s)
#define inf 0x3f3f3f3f
typedef long long ll;
#define pi acos(-1.0)
using namespace std;
#define mod (int)(1e9 + 7)
#define N (int)(1.1e5)

int f[700][700], c[700][700];
void fun(int x, int y) {
  int b = 0, i = x, j = y;
  while (y) {
    b++;
    int tmp = x % y;
    x = y;
    y = tmp;
  }
  c[i][j] = b;
  f[i][j] = b * x * x;
}
int main() {
#ifndef ONLINE_JUDGE
  //freopen("/Users/perpeternal/Documents/Sketch/data/in.dat", "r", stdin);
  // freopen("/Users/perpeternal/Documents/Sketch/data/out.dat","w",stdout);
#endif
  for1(i, 666) for1(j, 666) fun(i, j);
  int t;
  ind(t);
  while (t--) {
    int n, m, p;
    ll ans = 0;
    scanf("%d%d%d", &n, &m, &p);
    for1(j, m) {
      for (int i = 1; i <= j && i <= n; i++) {
        int k = (n - i) / j;
        int tt = c[i][j] * j * j / f[i][j];
        for (int q = 0; q < c[i][j]&&q<=k ; q++) {
          //if (i + q * j > n) break;
          //ll t = (n - (i + j * q)) / (c[i][j] * j) + 1;
          ll t=(k-q)/c[i][j]+1;
          ll tmp=(i+j*q)*j/f[i][j];
          ans=(ans+tmp*t%p+(t-1)*t/2%p*tt%p)%p;
          // ll b = (i + j * q) * j / f[i][j];
          // ans = (ans + b * t % p + (t - 1) * t / 2 % p * tt % p) % p;
        }
      }
    }
    printf("%lld\n", ans);
  }
  return 0;
}