题目链接: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;
}
分享到:
相关推荐
欧拉公式的证明, 学习了证明才能更好地理解和应用. V-E+F = 2 其中 V=顶点数 F=面数 E=棱数.
20210225-东吴证券-长城汽车-601633-看好欧拉品牌崛起.pdf
算法-数论- 欧拉函数.rar
hdu 1695 GCD(欧拉函数+容斥原理).docx
亲测有效 求解含有时滞的微分方程需要用到延迟微积分学的...(3)得到一个关于x(t), y(t)和z(t)的常微分方程组,利用数值求解方法如欧拉法或龙格-库塔法求解 (4)将 t 增加h,重复步骤1-3,直到求解到预设的终止时刻
欧拉函数 C语言实现 #include "iostream" #include "math.h" #define maxsize 100 using namespace std; typedef struct node { int num; int total; }struct_num; struct_num a[maxsize]; int is_prime(int n)
图论- 图的遍历- 欧拉通路与欧拉回路问题.rar
第八讲-机器人动力学--牛顿-欧拉方程.ppt
行业分类-设备装置-欧拉旋转定理演示教具.zip
长城汽车-601633-看好欧拉品牌崛起
算法-计算几何- 欧拉公式(包含源程序).rar
欧拉函数是数论中很重要的一个函数,欧拉函数是指:对于一个正整数 n ,小于 n 且和 n 互质的正整数(包括 1)的个数,记作 φ(n) 。 完全余数集合: 定义小于 n 且和 n 互质的数构成的集合为 Zn ,称呼这个集合为...
视频讲解欧拉定理和欧拉函数的证明。详细解释了证明简化剩余系的关系为什么要先证明完全剩余系的关系。以及欧拉函数的计算。
大数据-算法-基于欧拉方法的超高速撞击程序研制及碎片云相分布数值模拟.pdf
COMSOL 两相流 欧拉-欧拉 双流体模型
winker-Euler梁-弯曲波_欧拉梁_传递矩阵法_声子晶体_源码.zip
组合数学中经典定理 的实现 其中有: cayley定理 mobius 定理 欧拉函数 序数法 整数拆分等
密码 - 密码学复习 欧拉函数 一次同余式求解 本原根
计算机系统与网络安全技术06-152.2 欧拉定理(课件)_9.pptx