传送门：http://www.lydsy.com/JudgeOnline/problem.php?id=3994
【题解】
这是一个比较重要的等式，反演常见套路之一：
那么有了这个等式我们就可以感性推导化简
第一个等号到第二个等号待证。
然后我们又有，于是令
那么答案即为
接下来好像就是根号分段的事情了
暴力根号分段求下f，再暴力根号分段求每个询问即可。
安利一波，公式by leanote编辑器
复杂度O(nsqrt(n)+Tsqrt(n))
# include <stdio.h> # include <string.h> # include <algorithm> // # include <bits/stdc++.h> using namespace std; typedef long long ll; typedef long double ld; typedef unsigned long long ull; const int M = 5e5 + 10; const int mod = 1e9+7; # define RG register # define ST static int T, n, m; const int F = 50000; bool isnp[F + 10]; int p[F/3], pn=0, mu[F + 10]; ll s[F + 10], f[F + 10]; inline ll gF(int n) { ll ret = 0; for (int i=1, lst; i<=n; i=lst+1) { lst = n/(n/i); ret = ret + (ll)(n/i) * (lst-i+1); } return ret; } inline ll gG(int n, int m) { if(n > m) swap(n, m); ll ret = 0; for (int i=1, lst; i<=n; i=lst+1) { lst = min(n/(n/i), m/(m/i)); ret += (ll)(s[lst]-s[i-1])*(f[n/i]*f[m/i]); } return ret; } int main() { mu[1] = 1; for (int i=2; i<=F; ++i) { if(!isnp[i]) { p[++pn] = i; mu[i] = -1; } for (int j=1; j<=pn && i*p[j] <= F; ++j) { isnp[i*p[j]] = 1; if(i%p[j] == 0) { mu[i*p[j]] = 0; break; } mu[i*p[j]] = -mu[i]; } } for (int i=1; i<=F; ++i) s[i] = s[i-1] + mu[i], f[i] = gF(i); scanf("%d", &T); while(T--) { scanf("%d%d", &n, &m); printf("%lld\n", gG(n, m)); } return 0; } View Code转载于:https://www.cnblogs.com/galaxies/p/bzoj3994.html
相关资源：JAVA上百实例源码以及开源项目