Description 找出所有满足条件的(a,b)使得ab=k*(a+b) Input 一个整数k(1<=k<=1e9) Output 输出所有满足条件的(a,b)对数和每一对(a,b) Sample Input 2 Sample Output 3 3 6 6 3 4 4 Solution 问题转化为找k^2的所有因子，做法就是先对k分解素因数，对每个素因子的幂指数乘二即得到k^2的分解素因数形式，之后朴素的想法是2^res枚举因子(res是素因子总数)，但是这样会T也会重，所以要用二进制优化，即对每个素因子p，假设其幂指数是a，那么我们可以把a拆成1,2,…,2^x,b，b<2^(x+1)，那么通过这x+1个数的所有子集和可以表示1~a中所有数，相当于把k^2的素因子分解形式变成一个由较少数字构成的形式，而且这些较少数字的组合可以表示所有k^2的因子 Code
#include<cstdio> #include<iostream> #include<cstring> #include<algorithm> #include<cmath> #include<vector> #include<queue> #include<map> #include<set> #include<ctime> using namespace std; typedef long long ll; #define INF 0x3f3f3f3f #define maxn 111 ll f[maxn][2],ff[maxn]; typedef pair<ll,ll>P; map<P,int>ans; map<P,int>::iterator it; int res; int main() { ll k,n; while(~scanf("%I64d",&k)) { n=k; res=0; for(int i=2;i*i<=k;i++) if(k%i==0) { int temp=0; while(k%i==0)k/=i,temp++; f[res][0]=i,f[res++][1]=2*temp; } if(k>1)f[res][0]=k,f[res++][1]=2; int cnt=0; for(int i=0;i<res;i++) { ll m=f[i][1],k=1; ll p=f[i][0],temp; while(k<m) { temp=1; for(int j=0;j<k;j++)temp*=p; m-=k,k*=2; ff[cnt++]=temp; } if(m) { temp=1; for(int j=0;j<m;j++)temp*=p; ff[cnt++]=temp; } } ans.clear(); int N=1<<cnt; for(int i=0;i<N;i++) { ll b=1; for(int j=0;j<cnt;j++) if(i&(1<<j))b*=ff[j]; P temp=P(n+n*n/b,b+n); if(ans.find(temp)==ans.end())ans[temp]=1; } printf("%d\n",ans.size()); for(it=ans.begin();it!=ans.end();it++) { P temp=it->first; printf("%I64d %I64d\n",temp.first,temp.second); } } return 0; }