題意其實就是求出所有正整數對(a,b)使得a*b=k(a+b)
化簡之後可以得到(a-k)(b-k)=k^2
於是我們的目標就變成了找出k^2的正因數個數
code裡用的方法是先求出k的質因數分解,在構造所有正因數的集合的時候再讓他們的指數可以到2倍
但是現在想想好像直接把k^2抓來分解也是可以的,質數一樣求到sqrt(10^9)就好
#include<bits/stdc++.h> #define LL long long using namespace std; const int maxa=50000+5; vector<LL> prime,ans; LL vis[maxa],k; void solve() { LL m=sqrt(maxa),K=k; for(LL i=2;i<=m;i++) if(!vis[i]) for(LL j=i*i;j<maxa;j+=i) vis[j]=1; for(LL i=2;i<maxa;i++) if(!vis[i]) prime.push_back(i); ans.push_back(1); for(int i=0;i<prime.size();i++) { LL tmp=1,size=ans.size(),cnt=0; while(K%prime[i]==0) cnt++,K/=prime[i]; cnt*=2; while(cnt--) { tmp*=prime[i]; for(int j=0;j<size;j++) ans.push_back(tmp*ans[j]); } if(K==1) break; if(i==prime.size()-1 && K!=1) prime.push_back(K); } sort(ans.begin(),ans.end()); ans.resize(unique(ans.begin(),ans.end())-ans.begin()); //for(int i=0;i<ans.size();i++) printf("%I64d\n",ans[i]); printf("%d\n",ans.size()); for(int i=0;i<ans.size();i++) { printf("%I64d %I64d\n",ans[i]+k,k*k/ans[i]+k); //if(-ans[i]+k>0 && k*k/(-ans[i])+k>0) printf("%I64d %I64d\n",-ans[i]+k,k*k/(-ans[i])+k); } } int main() { scanf("%I64d",&k); solve(); }
沒有留言:
張貼留言