传送：http://codeforces.com/gym/101612
题意：给定一个数n（<=1e18），将n分解为若干个数的成绩。要求这些数两两之间的差值不能大于1。
分析：
若n==2^k，则答案一定是-1。
然后，考虑若n==a^k，枚举k，二分求a。若n==a^x*(a+1)^y，枚举x，y，二分求解a。
注意：两数相乘可能>1e18，特判。
1 #include<bits/stdc++.h> 2 using namespace std; 3 typedef long long ll; 4 typedef pair<ll,ll> pll; 5 typedef pair<pair<ll,ll>,ll> plll; 6 const int maxn=1e6+10; 7 const ll inf=1e18+1e6; 8 ll n; 9 vector<pll> g1; 10 vector<plll> g2; 11 ll mul(ll a,ll b){ 12 if (a>=1.0*inf/b) return inf; 13 else return a*b; 14 } 15 ll _pow(ll a,ll b){ 16 ll res=1,base=a; 17 while (b){ 18 if (b&1) res=mul(res,base); 19 base=mul(base,base); 20 b>>=1; 21 } 22 return res; 23 } 24 ll solve(int k){ 25 ll l=1,r=n,ans,mid; 26 while (l<=r){ 27 mid=(l+r)>>1; 28 ll tmp=_pow(mid,k); 29 if (tmp==n) return mid; 30 if (tmp<n) l=mid+1; else r=mid-1; 31 } 32 return 2; 33 } 34 ll solve2(int x,int y){ 35 ll l=1,r=n,ans,mid; 36 while (l<=r){ 37 mid=(l+r)>>1; 38 ll tmp=_pow(mid,x),tmp2=_pow(mid+1,y); 39 if (mul(tmp,tmp2)==n) return mid; 40 if (mul(tmp,tmp2)<n) l=mid+1; else r=mid-1; 41 } 42 return 2; 43 } 44 int main(){ 45 //freopen("little.in","r",stdin);freopen("little.out","w",stdout); 46 ios::sync_with_stdio(false); 47 cin >> n; 48 if (n==(n&(-n))) return cout << -1 << endl,0; 49 g1.clear(); g2.clear(); 50 ll num=0; 51 // a^k 52 for(int i=1;i<=63;i++){ 53 ll a=solve(i); 54 if (_pow(a,i)==n){ 55 g1.push_back({i,a}); 56 } 57 } 58 // a^x * (a+1)^y 59 for(int i=1;i<=63;i++){ 60 for (int j=1;j<=63;j++){ 61 ll a=solve2(i,j); 62 ll tmp=_pow(a,i),tmp2=_pow(a+1,j); 63 if (mul(tmp,tmp2)==n){ 64 g2.push_back({{i,j},a}); 65 } 66 } 67 } 68 cout << g1.size()+g2.size() << endl; 69 for (auto i:g1){ 70 ll tmp=i.first; 71 cout << tmp; 72 for (int j=0;j<tmp;j++) cout << " " << i.second; 73 cout << endl; 74 } 75 for (auto i:g2){ 76 ll tmp=i.first.first+i.first.second; 77 cout << tmp; 78 tmp=i.first.first; 79 for (int j=0;j<tmp;j++) cout << " " << i.second; 80 tmp=i.first.second; 81 for (int j=0;j<tmp;j++) cout << " " << i.second+1; 82 cout << endl; 83 } 84 return 0; 85 }