首页 > 代码库 > UVALive 5964 LCM Extreme(数学)
UVALive 5964 LCM Extreme(数学)
题目链接 ： http://vjudge.net/problem/viewProblem.action?id=29410
题意 ： 求∑lcm(i, j) (其中1 <= i < j <= n) n <= 5 * 10 ^ 6
做contest的时候一开始看到这道题目我想到贾教的线筛那篇论文上好像是讲到过这个的，然后就去翻了...到最后还是不理解怎么做 - -b
思路 ： 其实蛮简答的，首先你处理出这么一个数组sum[i]表示与i互质且比i小的数之和，那么sum[i] = (1+i)*i/2 - ∑sum[i/d] (其中d是i的所有非1约数)
这个可以利用类似筛素数筛的复杂度为O(n*log(n))。然后,所求的答案ans[n] = ans[n-1] + ∑sum[n/d]*d*n/d(其中d是n的所有约数) 这个递推式可以这样理解：sum[n/d]所求的和的那些数肯定和n是互质的，那么的话他们乘上d与n求gcd的话肯定就是d了，那么他们和n求lcm的话就是sum[n/d] * d(最大公约数) * n/d了，这个也是可以通过筛素数的方式地推出来的。
所以总体复杂度是O(n*log(n) + T)
代码 ：
1 #include <cstdio> 2 #include <cstring> 3 #include <algorithm> 4 #include <iostream> 5 6 using namespace std; 7 typedef unsigned long long lld; 8 const int MAXN = 5 * 1000005; 9 lld sum[MAXN];10 lld ans[MAXN];11 12 void solve(int N) {13 sum[0] = 0;14 for (int i = 1; i <= N; i++) {15 sum[i] = sum[i - 1] + i;16 }17 sum[1] = 0;18 for (int i = 2; i <= N; i++) {19 sum[i] -= i;20 for (int j = 2; j * i <= N; j++) {21 sum[j * i] -= sum[i] * j;22 }23 }24 memset(ans, 0, sizeof(ans));25 ans[1] = 0;26 for (int i = 2; i <= N; i++) {27 ans[i] += ans[i-1];28 for (int j = 1; i * j <= N; j++) {29 ans[j * i] += sum[i] * i * j;30 }31 }32 }33 34 int main() {35 solve(5000000);36 int T; scanf("%d", &T);37 for (int cas = 1; cas <= T; cas++) {38 int n; scanf("%d", &n);39 printf("Case %d: %llu\n", cas, ans[n]);40 }41 return 0;42 }
UVALive 5964 LCM Extreme(数学)
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。