Gym101612L Little Difference

题目链接：https://vjudge.net/problem/Gym-101612L

知识点：　　数学

题目大意：

　　给一个数 \(n(1 \le n \le 10^{18})\)，要求将 \(n\) 分解成 \(a^{p}(a+1)^{q}\)，问有多少种分解方案。

解题思路：

　　如果 \(n\) 可以表示成 \(2^{t}\) 的形式，则有无限种分解方案，因为此时 \(n\) 可以分解成 \(1^{p} \times 2^{t}\) 的形式，其中 \(p\) 可以为任意整数。

　　接下来讨论有限种分解方案的情况。

　　\(n=a^{p}(a+1)^{q}\) 中的 \(a\) 近似等于 \(\lfloor ^{p+q} \sqrt{n} \rfloor = \lfloor ^{r} \sqrt{n} \rfloor\)，其中 \((1 \le r \le log_2(n) \le 64)\)，用求出的近似的 \(a\) 和 \(a+1\) 去尝试分解 \(n\) 即可。

AC代码：

 #include <bits/stdc++.h>

 using namespace std;

 typedef long long LL;

 vector<vector<LL> > ans;

 void solve(LL n,LL a){//试分解函数

     vector<LL> ret;

     while(n%a==){

         ret.push_back(a);

         n/=a;

     }

     while(n%(a+)==){

         ret.push_back(a+);

         n/=(a+);

     }

     if(n==){

         ans.push_back(ret);

     }

 }

 int main(){

     freopen("little.in", "r", stdin);

     freopen("little.out", "w", stdout);

     LL n;

     scanf("%lld",&n);

     if((n&(n-))==){   //判断 n 是否是 1<<x 的形式的数

         printf("-1\n");

         return ;

     }

     solve(n,n);

     for(int s=;s<=;s++){

         LL r=(LL)pow(n,1.0/(double)s);

         for(int j=-;j<=;j++){

             if(r+j>)

                 solve(n,r+j);

         }

     }

     sort(ans.begin(),ans.end());

     ans.erase(unique(ans.begin(),ans.end()),ans.end()); //去重

     printf("%d\n",ans.size());

     for(int i=;i<ans.size();i++){

         printf("%d",ans[i].size());

         for(int j=;j<ans[i].size();j++){

             printf(" %lld",ans[i][j]);

         }

         printf("\n");

     }

     return ;

 }

巴特西

Gym101612L Little Difference

最新文章

热门文章