[Codeforces 100488C][2014-2015 Samara SAU ACM ICPC Quarterfinal Qualification Contest] Lost Temple

原題連結

題意其實就是求出所有正整數對(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();
}