线性筛素数 – Tgotp-Blog

2818: Gcd

首先知道

gcd(x,y) =  z

可化为

gcd(x/z,y/z) = 1;

那么令f[i] 为满足 gcd(x,y)= 1 (x,y <= i)的个数

那么答案就为 ∑ f[n/prime[i]]

观察发现 f[i] 为欧拉函数的前缀和。

那么线[......]

Read more

筛法

很久以前写了,但是没有传上来。两种方法

见代码:

 

POJ 2154 Color

首先,直接应用polya定理就可以得到ans=(N^gcd(0,N)+N^gcd(1,N)+…+N^gcd(N-1,N))/N,如果直接计算的话,即便应用快速幂,也改变不了循环计算N项和的复杂度。

于是便不得不从gcd的值入手看是否能合并一些项达到化简的目的了。尽管一共有N项,但gcd的值一定[......]

Read more