定理: 任何正整数n等于其因数的欧拉函数值之和,即∑d|nφ(d)=n 证明: 设一个集合{1/n,2/n,3/n,...,(n-1)/n,n/n} 对于上述的分式集合,若我们都将其化简至最简形式,设其中一个最简形式是a/b,那么我们一定有: b|n ① (a,b)=1 ② a<=b ③ 由②③可得,对于一个确定的b,它对应的a的个数为φ(b)(根据欧拉函数的定义:φ(n)=1到n中与n互质的数的个数) 那么我们再考虑,每一个最简形式a/b都是互相不同的,因为它们都是最简形式 而且,对于上述分数
10200 - Prime Time 此题极坑(本菜太弱),鉴定完毕,9遍过. 题意:很简单的求一个区间[a,b]内满足i*i+i+41(i>=a&&i<=b,0<=a<=b<=10000.)是素数的数有多个,求出百分比. 思路:直接裸判就行了(竟然不超时),但结果要加上1e-8(are you kidding me?). 下面来说说我怎么跪了,开始也是直接裸判,我
传送门 Longge's problem Time Limit: 1000MS Memory Limit: 65536K Total Submissions: 7327 Accepted: 2416 Description Longge is good at mathematics and he likes to think about hard mathematical problems which will be solved by some graceful algorithms.