UVALive - 7098 Farey Sums
來源：程序員人生 發布時間：2016-09-26 08:07:58 閱讀次數：2433次
題目：
這個題目考的就是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;
}
生活不易，碼農辛苦
如果您覺得本網站對您的學習有所幫助,可以手機掃描二維碼進行捐贈
