题面
传送门:UVa-11426
大致意思:输入一个正整数n,要求在时限为10sec内求出
保证答案在long long范围内
样例
Sample Input
10
100
200000
0
Sample Output
67
13015
143295493160
思路
引理:
如果要满足gcd(x,n)=i,其充分必要条件为gcd(x/i,n/i) = 1.
可以肯定的是,如果一个一个地枚举i,j <= n,时间复杂度为O(n^2)必然会T飞
我们可以设一个辅助函数 f(n) = gcd(1,n) + gcd(2,n) + …… + gcd(n-1,n);
那么答案S(n) = f(2) + f(3) + …… + f(n).
得出递推式
S(n) - S(n-1) = f(n).
∴问题转化为在线性时间内求出f(n)的大小.
可以发现,gcd(x,n) 因为 x < n,所以gcd(x,n)一定是n的约数
如果能将这些约数分类,继续刚才的套路,再去设一个辅助函数g(n,i)表示
gcd(x,n) = i 的x的个数
可以发现,f(n)=sigma(i * g(n,i))其中保证i是n的因数
由引理,可知道满足条件的x/i有phi(n/i)个
∴g(n,i) = phi(n,i).
至此,我们已经可以在sqrt(n) * n的时间内计算出f(n).
上述算法的代码如下.1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
using namespace std;
const int maxn = 4000010;
LL phi[maxn],f[maxn],S[maxn];
void phi_spawn(int x)
{
memset(phi,0,sizeof(phi));
phi[1] = 1;
for (int i = 2; i <= x; i++)
if (!phi[i])
{
for (int j = i; j <= x; j+=i)
{
if (!phi[j])
phi[j] = j;
phi[j] = phi[j] * (i-1) / i;
}
}
}
int calc(int x)
{
int ret = 0;
if (x == 1) return 1;
for (int i = 2; i <= sqrt(x+0.5); i++)
if (x % i == 0) ret += i*phi[x/i];
return ret;
}
int main(int argc, char *argv[])
{
phi_spawn(maxn);
memset(f,0,sizeof(f));
for (int i = 1; i <= maxn; i++)
f[i] = calc(i);
S[2] = f[2];
for (int i = 3; i <= maxn; i++) S[i] = S[i-1] + f[i];
int n;
while(scanf("%d",&n) == 1 && n)
printf("%lld\n",S[n]);
return 0;
}
但是在400W的数据下还是T飞了.还是菜啊.
但尽管如此还是有很多的重复计算，为什么呢？我们在枚举因数的时候，有很多次重复，
但是如果枚举因数,计算它的倍数,这样就几乎是一个筛法式的求f[n],对于每个i枚举倍数去更新f(n)
这样的算法将会与素数筛法的算法时间复杂度同阶.
正解代码
1 |
|
edited by karriganasta ❤ 20180209