国内最全IT社区平台 联系我们 | 收藏本站
华晨云阿里云优惠2
您当前位置:首页 > php开源 > php教程 > UVALive - 7098 Farey Sums

UVALive - 7098 Farey Sums

来源:程序员人生   发布时间:2016-09-26 08:07:58 阅读次数:1412次

题目:



这个题目考的就是1个对称性。

在a和b之间插入a+b,在b和a之间插入a+b

那末a/b+b/a就变成了a/(a+b)+(a+b)/b+b/(a+b)+(a+b)/a=a/b+b/a+3

增量是3,全部序列的增量是若干个3的和,这样的3的个数是n的欧拉函数的1半。

所以表达式很容易求出来,先求出前n个数的欧拉函数之和phi[n],然后答案便是(phi[n] * 3 ⑴)/ 2

代码:

#include<iostream> #include<stdio.h> using namespace std; int phi[10001]; void get_phi() { for (int i = 1; i <= 10000; i++)phi[i] = i; for (int i = 2; i <= 10000; i++) { if (phi[i] == i)for (int j = i; j <= 10000; j += i)phi[j] = phi[j] / i*(i - 1); phi[i] += phi[i - 1]; } } int main() { get_phi(); int p, n; scanf("%d", &p); for (int i = 1; i <= p; i++) { scanf("%d%d", &n, &n); printf("%d %d/2\n", i, phi[n] * 3 -1); } return 0; }

生活不易,码农辛苦
如果您觉得本网站对您的学习有所帮助,可以手机扫描二维码进行捐赠
程序员人生
------分隔线----------------------------
分享到:
------分隔线----------------------------
关闭
程序员人生