您好,欢迎访问代理记账网站
  • 价格透明
  • 信息保密
  • 进度掌控
  • 售后无忧

GCD - Extreme (II) UVA - 11426 (欧拉函数+一个数与所有小于它的数的gcd的和)

传送门

题意:给定2<=n<=4e6,求G

题解:UVA11426 GCD - Extreme (II) 欧拉函数应用

  • 先求一个数与所有小于它的数的gcd的和
  • 然后就是求前缀和的问题了

求一个数与所有小于它的数的gcd的和:

具体实现见代码

num[10]=1*phi[10]+2*phi[5]+5*phi[2] (所有除开自己的因数)。注意最需要理解的是 (抓住这个数是因数d的x/d倍数就ok了,gcd答案为d的数自然有phi(x/d)个,因为d*y,如果gcd(y,x/d)互质,gcd(d*y,x)才为d,刚好和求x/d的欧拉数组一样

代码:

#include <bits/stdc++.h>
#define int long long
#define dbg(x) cout << #x << "===" << x << endl
#define pb push_back
using namespace std;
const int N = 4e6 + 10;

int n;
int phi[N], num[N], sum[N];
void init(int n) {
    int i, j;
    //欧拉函数
    for (i = 2; i <= n; i++) {
        if (phi[i]) continue;  //非素数
        for (j = i; j <= n; j += i) {
            if (!phi[j]) phi[j] = j;
            phi[j] = phi[j] / i * (i - 1);
        }
    }
    // 求某个数与所有小于它的数的gcd的和
    for (i = 1; i <= n; i++)
        for (j = 2 * i; j <= n; j += i)
            num[j] += i * phi[j / i];  // num[i]为1~i-1种的数与i的gcd的和

    for (i = 1; i <= n; i++) sum[i] = sum[i - 1] + num[i];
}
signed main() {
    init(N - 1);
    while (cin >> n) {
        if (n == 0) break;
        cout << sum[n] << endl;
    }
    return 0;
}
/*
input:::
10
100
200000
0
output:::
67
13015
143295493160
*/

 


分享:

低价透明

统一报价,无隐形消费

金牌服务

一对一专属顾问7*24小时金牌服务

信息保密

个人信息安全有保障

售后无忧

服务出问题客服经理全程跟进