首页 > 代码库 > uva 11426 - GCD - Extreme (II)(数论)
uva 11426 - GCD - Extreme (II)(数论)
题目链接:uva 11426 - GCD - Extreme
题目大意:给出n,求∑i!=jngcd(i,j)
解题思路:f(n)=gcd(1,n)+gcd(2,n)+?+gcd(n?1,n)
S(n)=f(2)+f(3)+?+f(n)
S(n)=S(n?1)+f(n)
问题转化成怎么求f(n),对于一个n来说,枚举因子乘上个数即可。
#include <cstdio>
#include <cstring>
const int N = 4000000;
typedef long long ll;
int phi[N+5];
ll s[N+5], f[N+5];
void phi_table(int n) {
for (int i = 2; i <= n; i++)
phi[i] = 0;
phi[1] = 1;
for (int i = 2; i <= n; i++) {
if (!phi[i]) {
for (int j = i; j <= n; j += i) {
if (!phi[j])
phi[j] = j;
phi[j] = phi[j] / i * (i-1);
}
}
}
}
int main () {
phi_table(N);
memset(f, 0, sizeof(f));
for (int i = 1; i <= N; i++) {
for (int j = i * 2; j <= N; j += i) {
f[j] += i * phi[j/i];
}
}
s[2] = f[2];
for (int i = 3; i <= N; i++)
s[i] = s[i-1] + f[i];
int n;
while (scanf("%d", &n) == 1 && n) {
printf("%lld\n", s[n]);
}
return 0;
}
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。