专栏首页Don的成长史【小米OJ】纯位数

【小米OJ】纯位数

在数学中,所谓“纯位数”是指由相同位元重复而组成的自然数。比如在十进制中,1,22,333,555 都是纯位数。 很显然,15 在十进制中不是一个纯位数,但是在二进制 15(10) = 1111(2) 却是一个纯位数。

一个显然的事实是,对于正整数 N,其在 N+1 进制中必然是一个一位数,也就必然是个纯位数。

对于一个正整数 N,试找出使其成为纯位数的最小进制 K。

输入描述:

一个正整数 N (0 < N < 10^8)

输出描述:

使 N 为纯位数的最小进制 K

输入样例:

22
15

输出样例:

10
2

解题思路:

嗐 在小米OJ上分,有一点特别恶心,那就是数据都没有给定的范围。说下这题踩的坑吧我刚开始以为这题是2~16进制的转换,后来发现有个测试点是45322,预期输出是36,再比如测试点输入876569,预期输出是876548。还有一个坑就是测试点输入1。

AC代码WA代码:

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

string DecToX(ll n,ll x)  //将10进制的n转换成x进制的字符串
{
    string ans = "";
    do{
        ll t = n%x;
        n /= x;
        ans += (t>=0&&t<=9) ? t+'0' : t-10+'a';
    }while(n);
    reverse(ans.begin(),ans.end());
    return ans;
}

bool isPure(string s)   //判断是不是纯位数
{
    map<char,int> m;
    for(int i = 0; i < s.length(); i++)
    {
        m[s[i]]++;
    }
    return m.size()==1;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    //有个测试用例没过:输入: "876569",期望输出: "876568"
    ll n;
    while(cin >> n)
    {
        for(ll i = 2; i <= n; i++) 
        {
            if(isPure(DecToX(n,i)))
            {
                cout << i << endl;
                break;
            }
        }
    }
    return 0;
}

AC代码:

#include <bits/stdc++.h>
using namespace std;

bool isPure(int n,int x)  //判断x进制的n是不是纯位数
{
    int t = n%x;
    while(n%x==t)
    {
        n /= x;
    }
    return n==0;   
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    int n;
    while(cin >> n)
    {
        for(int i = 2; i <= n+1; i++)  //若写成i<=n,n=1时会有bug无输出
        {
            if(isPure(n,i))
            {
                cout << i << endl;
                break;
            }
        }
    }
    return 0;
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • HBU-DS2018SY-1-1 数组循环左移 (20 分)

    版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。 ...

    喜欢ctrl的cxk
  • 【PAT乙级】判断题

    版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。 ...

    喜欢ctrl的cxk
  • 【PAT乙级】数组元素循环右移问题

    版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。 ...

    喜欢ctrl的cxk
  • LeetCode(一)

    Given an array of integers, return indices of the two numbers such that they add...

    Rekent
  • Leercode 35 Search Insert Position

    Given a sorted array and a target value, return the index if the target is foun...

    triplebee
  • 数据结构与算法-快速排序算法

    版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。 ...

    cwl_java
  • LeetCode Weekly Contest 37解题思路

    版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.n...

    用户1147447
  • 用 WPF 写的颜色拾取器

    之前都是用别人的颜色拾取器,今天自己用WPF写了一个颜色拾取器小程序 拾取鼠标所在位置的颜色,按键盘上的空格键停止取色 程序下载:MyWPFScreenColo...

    lpxxn
  • poj-3660-cows contest(不懂待定)

    N (1 ≤ N ≤ 100) cows, conveniently numbered 1..N, are participating in a program...

    瑾诺学长
  • 算法复杂度分析

    为什么要进行算法分析? 预测算法所需的资源 计算时间(CPU 消耗) 内存空间(RAM 消耗) 通信时间(带宽消耗) 预测算法的运行时间 在给定输入规模时,所执...

    前朝楚水

扫码关注云+社区

领取腾讯云代金券