Acwing聪明的燕姿

Acwing聪明的燕姿

/

题意

题目的大意就是给一个数S

让你找到有多少数能够满足它约数的和等于S

比如S = 42

这个时候就有3个数满足条件

41 = (1 + 41) == 42
20 = (1 + 2 + 4 + 5 + 10 + 20) == 42
26 = (1 + 2 + 13 + 26) == 42

思路

N = P1^a1 * P2^a2 * … * Pn^an
则N的约数个数为(a1+1)(a2+1)…(an+1)

假设N的一个约数为D

D = P1^b1 * P2^b2 * … * Pn^bn
其中bi可以取到0，范围是0<= bi <= ai

因为只有和N的质因数一一对应一定能得到约数
因为bi可以从0取到ai,那么每一个bi就有(ai+1)种选法

约数的个数就是每个bi对应多少种选法相乘
即约数个数就为(a1+1)(a2+1)…(an+1)

约数之和S = (1+p1+p1^2+…+p1^a1)(1+p2+p2^2+…+p2^a2)…(1+pn+pn^2+…+pn^an)

这个怎么理解呢

因为每一个约数为D = P1^b1 * P2^b2 * … * Pn^bn

那么S = (1+p1+p1^2+…+p1^a1)(1+p2+p2^2+…+p2^a2)…(1+pn+pn^2+…+pn^an)

这个公式的意思就是从每个括号里面取出来一个数然后相乘，就能得到一个约数Di
然后所有的约数Di相加就得到约数之和S
举个例子

对于S = 42来说，42对应的结果里面有一个为20，20 = (1 + 2 + 4 + 5 + 10 + 20)
20 = 2^2*5
对于两个质因数2和5来说
2可以取0,1,2次，5可以取0,1次
所以S = (1+2+2^2)(1+5) = 42

所以我们最暴力的想法一定就是枚举了，比如对一个数S
枚举从1到S-1的所有数的约数，再判断他们的约数和是否等于S

但是这么做显然会超时，因为1 <= S <= 2*10^9

这个时候我们就可以观察我们的约数和的公式
S = (1+p1+p1^2+…+p1^a1)(1+p2+p2^2+…+p2^a2)…(1+pn+pn^2+…+pn^an)

假设这个时候有一个约数和S满足(1+2)(1+2+2^2)(1+2+2^2+…+2^k)
3x5x9x17x33x65x129 = 635037975 就已经接近1e9的量级了，可见符合条件的项不会很多

那么这个时候我们就可以用dfs进行搜索，看我们能不能得到符合条件的(1+pk+pk^2+…+pk^ak)能够使得
S能够整除，即S % (1+pk+pk^2+…+pk^ak) == 0
然后S /= (1+pk+pk^2+…+pk^ak),再dfs到下一层

先附上源码

#include<bits/stdc++.h>
using namespace std;
const int N = 5e4;
int cnt,primes[N];
bool st[N];
int ans[N],len;
void get_primes(int x)
{for(int i=2;i<=x;i++){if(!st[i]) primes[cnt++]=i;for(int j=0;primes[j]*i<=x;j++){st[primes[j]*i]=true;if(i%primes[j]==0) break;}}
}
bool is_prime(int x)
{if(x<N) return !st[x];for(int i=0;primes[i]<=x/primes[i];i++)if(x%primes[i]==0) return false;return true;
}
void dfs(int last,int prod,int s)
{if(s==1) {ans[len++]=prod;return ;}if(s-1>(last<0?1:primes[last])&&is_prime(s-1))ans[len++]=prod*(s-1);for(int i=last+1;primes[i]<=s/primes[i];i++){int p=primes[i];for(int j=1+p,t=p;j<=s;t*=p,j+=t)if(s%j==0)dfs(i,prod*t,s/j);}
}
int main()
{get_primes(N-1);int s;while(cin>>s){len=0;dfs(-1,1,s);cout<<len<<endl;if(len){sort(ans,ans+len);for(int i=0;i<len;i++) cout<<ans[i]<<' ';cout<<endl;}}return 0;
}

我们可以对其剪枝：

当 s=1+pi时，这时可以结束了，pi是质数，pi=s-1,只用判断s-1是否是质数即可，并且要大于上一个质数，因为对于质数我们是从小到大枚举的，之前枚举过的之后不可再选。

另一大类情况又分两种

又S只会有两种情况，就是一种情况包括一个因子里面有(1+Pi)，另一种情况不包括(1+Pi)
S = (1+Pi)(1+Pj+Pj^2.....)
S = (1+Pi+Pi^2)(1+.....)

但是这两种情况都可以看出来Pi ^2 <= S
所以我们dfs枚举Pi的上限就是根号s

所以dfs应该设置成三个参数dfs(last,product,S)

last:上一个质数；

s:表示剩余的s(被因子除过后)

product: 从整体来讲表示s的各因子的乘机，在第二个for循环中要乘上(1+Pj+Pj^2.....)

乘到最后product应该满足孙燕姿的数。