题意：一个项链有n个珠子，每个珠子为黑色或白色。问有多少种不同的项链？
注意，n的数量十分大，因此，我们枚举i(1<=i<=n)，令L=n/i，求出L的欧拉函数，则这些数和L互质，因此gcd（k,n)=i的k一共有L的欧拉函数个，这是一个很聪明的转换方式，而且这题需要高精度。最终答案就是Σ(2^i*K)/n，K为(n/i)的欧拉函数。
代码：太长不敢打，怕改个一天都改不出来。
本文共 240 字，大约阅读时间需要 1 分钟。
题意：一个项链有n个珠子，每个珠子为黑色或白色。问有多少种不同的项链？
注意，n的数量十分大，因此，我们枚举i(1<=i<=n)，令L=n/i，求出L的欧拉函数，则这些数和L互质，因此gcd（k,n)=i的k一共有L的欧拉函数个，这是一个很聪明的转换方式，而且这题需要高精度。最终答案就是Σ(2^i*K)/n，K为(n/i)的欧拉函数。
代码：太长不敢打，怕改个一天都改不出来。
转载于:https://www.cnblogs.com/qzqzgfy/p/5528420.html