UVA11752 The Super Powers

深藏阁楼爱情的钟 2022-09-20 12:44 28阅读 0赞

最近几天的状态着实不好，数电设计的答辩不能更逗，万幸是终于到家了，看到群里有各种群赛十分开心，希望能找回刷题的动力，调整下状态。

这道题是很久前做的，细节记不太清了。。。

数据范围1到 2^64 -1，可以看出需要用 unsigned long  long ，其中1单独考虑，仔细分析可知满足条件的数必然是一个数的合数次方，最小是4，一个数的4次方在2^64 -1之内，那最大只能到65535。暴力枚举然后去除重复的就行了。可以用limit=ceil( 64/(log(i)/log(2)) )-1来判断一个数乘方数的上界。

去重我用的是STL的set，用数组排序再用unique函数也行。

#include <cstdio>
    #include <cmath>
    #include <algorithm>
    #include <set>
    using namespace std;
    
    #define i64u unsigned long long
    
    int heshu[50]={4,6,8,9,10,12,14,15,16,18,20,21,22,24,25,26,27,28
                ,30,32,33,34,35,36,38,39,40,42,44,45,46,48,49,50,51,52,54,55,56,57,58,60,62,63,64};
    
    i64u POW (i64u s,i64u index)
    {
        i64u ans=1;
        while (index>=1)
        {
            if ((index&1)==1)   //奇数
                ans=(ans*s);
            index>>=1;
            s=s*s;
        }
        return ans;
    }
    set<i64u> s;
    
    int main ()
    {
        int id=0,i;
        printf("1\n");
        for (i=2;i<65536;i++)
        {
            int limit;
            if (i==2) limit=63;
            else limit=ceil( 64/(log(i)/log(2)) )-1;
            if (limit <4) break;
            for (int j=0;heshu[j]<=limit;j++)
                s.insert(POW(i,heshu[j]) );
        }
        set<i64u>::iterator it;
        for (it=s.begin();it!=s.end();it++)
            printf("%llu\n",*it);
        return 0;
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，28人围观）

还没有评论，来说两句吧...

相关阅读

相关【UVa#10325】The Lottery

Description [UVa\10325][UVa_10325] 给定n和m个数，求1~n中不被这m个数中任意一个数整除的数的个数 Solution 容斥原

青旅半醒/ 2023年06月05日 08:54/ 0 赞/ 25 阅读

相关 J. The Power of the Dark Side - 2

题意 tournament 锦标赛 agility 敏捷 intelligence 智力 strength 力量 parameter 参数 restrictio

深藏阁楼爱情的钟/ 2022年10月19日 00:52/ 0 赞/ 124 阅读

相关 UVa 1374 Power Calculus （快速幂计算）

题意：给出x和正整数n，问最少需要几次乘除法可以得到n = x^m //打表法对1~1000的数打表 include <iostream> include

分手后的思念是犯贱/ 2022年09月27日 15:29/ 0 赞/ 159 阅读

相关 UVA11752 The Super Powers

最近几天的状态着实不好，数电设计的答辩不能更逗，万幸是终于到家了，看到群里有各种群赛十分开心，希望能找回刷题的动力，调整下状态。这道题是很久前做的，细节记不太清了。。。

深藏阁楼爱情的钟/ 2022年09月20日 12:44/ 0 赞/ 29 阅读

相关近期简单题目小结 UVA 100+HDU 2007+URAL 1084+Poj 1152+UVA 10042+UVA 11752+UVA 10780

新年练习赛(http://acm.hust.edu.cn/vjudge/contest/view.action?cid=40140\overview密码password)和之前

我不是女神ヾ/ 2022年08月24日 14:18/ 0 赞/ 166 阅读

相关 uva 10515——Powers Et Al.

题意：这个题目题中的图片已经给的够清楚了，就算不怎么读题，也能yy大概的意思，况且题目也很短，很容易都出来就是给定 a，b，然后求a^b的个位数！思路：开始想到了同

绝地灬酷狼/ 2022年08月09日 13:48/ 0 赞/ 67 阅读

相关 uva 10622——Perfect P-th Powers

题意：给定一个数n，求最大的一个数k使得n=x^k。思路1：正规的做法是把这个素数分解，然后求指数的最大公约数就是所求（听说有人取了最小值也能过，数据水吧！），素数

小灰灰/ 2022年08月09日 13:48/ 0 赞/ 185 阅读

相关 uva 11752 -The Super Powers (数论)

We all know the Super Powers of this world and how they manage to get advantages in poli

港控/mmm°/ 2022年08月09日 12:55/ 0 赞/ 144 阅读

相关 UVA 12297 Super Poker（矩阵快速幂）

想到了一个递推式 f(n,k)=f(n−k,k)\+f(n−k,k−1)∗4\+f(n−k,k−2)∗6\+f(n−k,k−3)∗4\+f(n−k,k−4) 这

向右看齐/ 2022年08月05日 05:10/ 0 赞/ 158 阅读

相关 UVA 12298——Super Poker II

题意：给定一些扑克牌，问这些扑克牌选四色能组成n的方案数，其中遗失了c张牌，这c张不能用，问n从a到b的方案数。思路：分析每一种花色，那么每种花色组成的方案

雨点打透心脏的1/2处/ 2022年07月19日 11:56/ 0 赞/ 76 阅读