LightOJ - 1236 Pairs Forming LCM（质因数分解找规律+容斥）

传送门

---

题目大意

求${\sum }_{i=1}^n{\sum }_{j=i}^n[lcm(i,j)==n],n\le 1e^{14}$

解题思路

一开始以为是莫比乌斯反演，推了一下发现推不动了。尝试找下规律，对$n$质因数分解$n=p_1^{a_1}{p}_2^{a_2}...p_n^{a_n}$，然后考虑$lcm$在质因数分解下的意义，实际上就是$i\ast j$后每一个素数一定有$p_k^{max(b_i,b_j)}=p_k^{a_k}$，即$max(b_i,b_j)=a_k$。这样感觉规律就在眼前了，我尝试打表却还是没找出来…

实际上是有技巧的，考虑${\sum }_{i=1}^n{\sum }_{j=1}^n[lcm(i,j)==n]$，这时再考虑上面的想法，显然是每一个$p_k^{a_k}$一定在$i,j$其中之一上可以分解得到，对于另外一个数那么可选择的$p_k$的指数的取值范围就是$[0,a_k]$，那么考虑乘法原理最后的答案就是$(2a_1+1)(2a_2+1)...(2a_n+1)$

但是本题相对于上述答案不同的是只有$j\ge i$，然而当$i=j$时显然只有$i=j=n$这一种情况，考虑容斥定理，且上述若干个奇数的乘积一定是奇数，那么$j\ge i$的贡献就是$(ans-1)/2$，那么最终的答案就是$(ans-1)/2+1$

这题数据巨毒瘤，我用了很久自认为完美无缺的Pollard-Rho板子被卡了

// // Created by Happig on 2020/10/21 // #include <bits/stdc++.h> #include <unordered_map> #include <unordered_set> using namespace std; #define fi first #define se second #define pb push_back #define ins insert #define Vector Point #define ENDL "\n" #define lowbit(x) (x&(-x)) #define mkp(x, y) make_pair(x,y) #define mem(a, x) memset(a,x,sizeof a); typedef long long ll; typedef long double ld; typedef unsigned long long ull; typedef pair<int, int> pii; typedef pair<ll, ll> pll; typedef pair<double, double> pdd; const double eps = 1e-8; const double pi = acos(-1.0); const int inf = 0x3f3f3f3f; const double dinf = 1e300; const ll INF = 1e18; const int Mod = 1e9 + 7; const int maxn = 1e7 + 10; int prime[maxn / 3], cnt; bitset<maxn> vis; void euler() { vis[1] = 1; for (int i = 2; i < maxn; i++) { if (!vis[i]) prime[++cnt] = i; for (int j = 1; j <= cnt && 1LL * i * prime[j] < maxn; j++) { vis[i * prime[j]] = 1; if (i % prime[j] == 0) break; } } } ll solve(ll n) { int m = sqrt(n + 0.5); ll ans = 1; for (int i = 1; i <= cnt && prime[i] <= m; i++) { if (n % prime[i] == 0) { ll res = 0; while (n % prime[i] == 0) { res++; n /= prime[i]; } ans *= 2 * res + 1; } if (n == 1) break; } if (n > 1) ans *= 3; return (ans - 1) / 2 + 1; } int main() { //freopen("in.txt","r",stdin); //freopen("out.txt","w",stdout); ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0); int T, kase = 0; ll n; euler(); cin >> T; while (T--) { cin >> n; cout << "Case " << ++kase << ": " << solve(n) << ENDL; } return 0; }