ZOJ 3673

思路：要求满足的m=a³+b³=(a+b)(a²-ab+b²)的(a,b)组合。

令t=a+b,则t一定是m的约数，所以应枚举m的所有约数。

然后可以得到

a+b=t

ab=(t²-m/t)/3=p

继而转化为a²-ta+p=0是否有正整数解就可以了。

再就是注意范围要用unsigned long long。

代码：

  1 #include<cstdio>
  2 #include<cmath>
  3 #include<algorithm>
  4 #include<iostream>
  5 #define ll unsigned long long
  6 #define M 5000001
  7 #define mm 2641636
  8 using namespace std;
  9 int cnt,num,cn;
 10 ll prime[M],p[100],e[100];
 11 bool f[M];
 12 ll n;
 13 struct point
 14 {
 15     ll a,b;
 16     bool operator<(const point &aa) const
 17     {
 18         return a<aa.a;
 19     }
 20 }an[1000];
 21 void init()
 22 {
 23     cnt=0;
 24     for(int i=2;i<M;i++){
 25         if(!f[i]) prime[cnt++]=i;
 26         for(int j=0;j<cnt&&i*prime[j]<M;j++){
 27             f[i*prime[j]]=1;
 28             if(i%prime[j]==0) break;
 29         }
 30     }
 31 }
 32 void fac(ll m)
 33 {
 34     num=0;
 35     for(ll i=0;i<cnt&&(ll)prime[i]*prime[i]<=m;i++){
 36         if(m%prime[i]==0){
 37             p[num]=prime[i];
 38             ll j=1;
 39             m/=prime[i];
 40             while(m%prime[i]==0){
 41                 j++;
 42                 m/=prime[i];
 43             }
 44             e[num++]=j;
 45         }
 46     }
 47     if(m>1){
 48         p[num]=m;
 49         e[num++]=1;
 50     }
 51 }
 52 ll ispw2(ll a)
 53 {
 54     ll b=sqrt(1.0*a);
 55     if((ll)b*b==a) return b;
 56 //    if((ll)(b+1)*(b+1)==a) return b+1;
 57     return M;
 58 }
 59 bool IS(ll a,ll b)
 60 {
 61     for(int i=0;i<cn;i++)
 62         if(an[i].a==a&&an[i].b==b) return 1;
 63     return 0;
 64 }
 65 void is(ll t)
 66 {
 67     ll x1,x2;
 68     ll p=n/t;
 69     ll a=t*t-p;
 70     if(a>0&&a%3!=0) return ;
 71     ll m=a/3;
 72 //    cout<<t<<' '<<m<<endl;
 73     ll b=t*t-4*m;
 74     if(b<0) return ;
 75     ll c=ispw2(b);
 76     if(c==M) return ;
 77     if((t+c)%2==0){
 78         x1=(t+c)/2;
 79         x2=t-x1;
 80         if(x1>x2) swap(x1,x2);
 81         if(x1>0&&x1<t&&x1<mm&&x2<mm&&x2>0&&x2<t&&!IS(x1,x2)){
 82             an[cn].a=x1;
 83             an[cn++].b=x2;
 84         }
 85     }
 86     if(t-c>0&&(t-c)%2==0){
 87         x1=(t-c)/2;
 88         x2=t-x1;
 89         if(x1>x2) swap(x1,x2);
 90         if(x1>0&&x1<t&&x1<mm&&x2<mm&&x2>0&&x2<t&&!IS(x1,x2)){
 91             an[cn].a=x1;
 92             an[cn++].b=x2;
 93         }
 94     }
 95 //    cout<<t<<endl;
 96 }
 97 ll pw(ll a,ll b)
 98 {
 99     ll ans=1;
100     while(b){
101         if(b&1) ans*=a;
102         b>>=1;
103         a*=a;
104     }
105     return ans;
106 }
107 void dfs(int m,ll s)
108 {
109     is(s);
110     if(m>=num) return;
111     for(int i=0;i<=e[m];i++)
112         dfs(m+1,(ll)s*pw(p[m],i));
113 }
114 int main()
115 {
116 //    freopen("in.txt","r",stdin);
117 //    freopen("out.txt","w",stdout);
118     init();
119     while(scanf("%llu",&n)!=EOF){
120 //        cout<<n<<endl;
121         fac(n);
122         cn=0;
123         dfs(0,1);
124         sort(an,an+cn);
125         printf("%d",cn);
126         for(int i=0;i<cn;i++)
127             printf(" (%llu,%llu)",an[i].a,an[i].b);
128         printf("
");
129     }
130     return 0;
131 }

View Code