【题目描述】 kkk参加了NOI2333，结果被虐爆了！最简单的题目要求输入两个整数x和y，输出一个函数f(x,y)=F[x^y]^F[x]^F[y]（F[i]代表斐波那契数列的第i项），而且x和y都在1到N（N是给定的数）以内！kkk急的抓耳挠腮，于是只好交表。但是比赛有代码长度限制！这么大的表无法提交（怎么打出来都是个问题）！所以kkk只能删掉一些表（而且删掉所有换行）以缩短代码。 但是kkk发现，这道题目可以根据f(x,y)用O(1)的算法算出f(x*k,y*k)，其中k是任意正整数。别管这个规律是kkk是肿么发现的，也别管它对不对（肯定不对嘛），只要你——lzn——kkk的作弊帮手知道就可以了。所以，某些f函数是没有必要保存的，需要时调出其他的f函数计算下就可以了。 给出N，你需要求出最短的表里有多少个元素。 【输入格式】 有多组数据，每组数据包含一个整数N 【输出格式】 对于每组数据输出元素个数 【样例输入】 2 5 【样例输出】 3 19 【数据范围】 1<=N<=50000 【分析】 不难看出此题可以简化为：给出N，求有多少组(x,y)满足1<=x,y<=n且x和y互质。 可以发现，除了(1,1)外，其他的(x,y)都不相等。于是设满足x<=y-1的情况有f[n]个，则答案就是2*f[n]+1。 这里引入欧拉phi函数。 于是可以知道，
const maxn=50000; var phi,psum:array[0..maxn+1]of longint; i,n:longint; procedure table(n:longint); var i,j:longint; begin phi[1]:=0; for i:=2 to n do if phi[i]=0 then begin j:=i; while j<=n do begin if phi[j]=0 then phi[j]:=j; phi[j]:=phi[j] div i*(i-1); j:=j+i; end; end; end; begin table(maxn); psum[0]:=0; for i:=1 to maxn do psum[i]:=psum[i-1]+phi[i]; readln(n); writeln(2*psum[n]+1); end.转载于:https://www.cnblogs.com/JRX2015U43/p/6533513.html
相关资源：JAVA上百实例源码以及开源项目