欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

洛谷题解 P1010 【幂次方】

程序员文章站 2022-05-08 22:52:32
...

在我的博客食用效果更佳!https://www.cbw2007.tk/articles/luogu-P1010-sol/,文章最初发表于201975月12日。更多见在不同的网站浏览本站内容

原题链接: P1010 幂次方 - 洛谷 | 计算机科学教育新生态

分析

看各位大佬都用二进制等高端算法,蒟蒻都不会啊!QAQ只好用了最朴素的递归与模拟。

这里要理清这两点:

  1. 在分解一个数时,不能出现重复的,因为2x+2x=2x+12^x+2^x=2^{x+1}
  2. 分解出来的幂的指数要尽可能的大。

然后,程序的具体思路是:

  1. 先找一个尽可能大的幂。
  2. 特判,将指数为0和1的单独挑出来输出。
  3. 递归指数。
  4. 减去已经找到的幂次方数,返回第一步。

这样说可能有点迷,上代码更简单!

核心代码

void dfs(int k)//传入一个数
{
    while (k!=0)//如果这个数还没有处理完
    {
        int t=2,i;//指数为1
        for (i=1;t<=k;i++)//指数不断增加,直到当前幂次方已经大于k
            t*=2;
        i--; t/=2;//因为这时候t已经比k大了,所以指数减一
        if (i==0)//如果指数为零
        {
            cout<<"2(0)";
            k-=1;//同k-=t
            goto last;
        }
        if (i==1)//如果指数为一
        {
            cout<<"2";
            k-=2;//同k-=t
            goto last;
        }
        cout<<"2(";
        dfs(i);//递归指数
//		cout<<i;//可以把这一步取消注释,把上一步进行注释,观察指数未分解时是否正确
        cout<<")";
        k-=t;//减去已经找到的幂次方数
        last:
        if (k!=0)
            cout<<"+";//如果k没处理完,输出加号
    }
}