首页 > 代码库 > uva 11317 - GCD+LCM(欧拉函数+log)
uva 11317 - GCD+LCM(欧拉函数+log)
题目链接:uva 11317 - GCD+LCM
题目大意:给定n,求出1~n里面两两的最大公约的积GCD和最小公倍数的积LCM,在10100进制下的位数。
解题思路:在n的情况下,对于最大公约数为i的情况又phi[n/i]次。求LCM就用两两乘积除以GCD即可。
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;
typedef long long ll;
const int maxn = 1000000;
const double logt = log(10.0);
int N;
double g[maxn+5], s[maxn+5];
int phi[maxn+5];
void phi_table (int n) {
memset(phi, 0, sizeof(phi));
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);
}
}
}
}
void init (ll n) {
for (int i = 1; i <= n; i++) {
double tmp = log(i);
for (int j = 2 * i; j <= n; j += i)
g[j] += phi[j/i] * tmp;
}
for (int i = 1; i <= n; i++)
g[i] += g[i-1];
for (int i = 1; i <= n; i++)
g[i] /= logt;
}
int main () {
phi_table(maxn);
init(maxn);
int cas = 1;
while (scanf("%d", &N) == 1 && N) {
double ans = 0;
for (int i = 1; i <= N; i++)
ans += (N-1) * log(i);
ans /= logt;
ans -= g[N];
printf("Case %d: %lld %lld\n", cas++, (ll)(g[N] / 100) + 1, (ll)(ans / 100) + 1);
}
return 0;
}
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。