题目链接:https://ac.nowcoder.com/acm/problem/23616
解题思路:
O(nm)算法超时,使用莫比乌斯反演把时间复杂度降低成线性。
目前做的题目当中,要使用莫比乌斯反演的题目通常是答案是关于gcd的题目且数据规模大,暴力卒。
*推导过程:**
代码:
#include<bits/stdc++.h> using namespace std; typedef long long ll; const int MAXN = 1e6+7; const int mod = 1000000007; int prime[MAXN], prime_tot; bool prime_tag[MAXN]; int mu[MAXN]; ll sum[MAXN]; void pre_calc(int lim) { mu[1] = 1; for(int i = 2; i <= lim; i++) { if(!prime_tag[i]) { prime[++prime_tot] = i; mu[i] = -1; } for(int j = 1; j <= prime_tot; j++) { if(i * prime[j] > lim) break; prime_tag[i * prime[j] ] = true; if(i % prime[j] == 0) { mu[i * prime[j]] = 0; break; } else { mu[i * prime[j]] = -mu[i]; } } } } int main() { int n, m; scanf("%d %d",&n,&m); int minn = min(n,m); int maxn = max(n,m); pre_calc(maxn); for(int i = 1; i <= minn; i++) { for(int j = 1; i * j <= minn; j++) { sum[i * j] = (sum[i * j] + (1LL*mu[j]*i*i) % mod ) % mod; } } ll ans = 0; for(int k = 1; k <= minn; k++) { ans = (ans + (1LL*(n/k)*(m/k))%mod * (sum[k] % mod)) % mod; } printf("%lld\n",ans); }