51NOD 1116 K进制下的大数(字符串取模 + 枚举)

传送门
1116 K进制下的大数
基准时间限制:1 秒 空间限制:131072 KB 分值: 20 难度:3级算法题 收藏 关注
有1个字符串S,记录了1个大数,但不知这个大数是多少进制的,只知道这个数在K进制下是K – 1的倍数。现在由你来求出这个最小的进制K。
例如:给出的数是A1A,有A则最少也是11进制,然后发现A1A在22进制下等于4872,4872 mod 21 = 0,并且22是最小的,因此输出k = 22(大数的表示中A对应10,Z对应35)。
Input
输入大数对应的字符串S。S的长度小于10^5。
Output
输出对应的进制K,如果在2 – 36范围内没有找到对应的解,则输出No Solution。
Input示例
A1A
Output示例
22

解题思路:
其实我们就是枚举从出现的最大的数+1开始枚举,1直到36结束,然后基本操作就是对字符串取模,1个字符串进行取模,我们每次只需要乘以它的进制位数,然后1次累加进行取模就ok了,由于取模运算可以分开计算。(其实这个题我觉得主要是考察字符串取模的问题)

上代码:

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>

using namespace std;
const int MAXN = 1e5+5;
char s[MAXN];
int main()
{
while(cin>>s)
{
int len = strlen(s), Max = -1;
for(int i=0; i<len; i++)
{
if(s[i]>='A' && s[i]<='Z')
Max = max(Max,(s[i]-'A'+10));
else
{
Max = max(Max,(s[i]-'0'));
}
}
///cout<<Max<<endl;
if(Max == 0)///(在这里特判1下,其实不用特判也能过)
{
puts("No Solution");
continue;
}
for(int i=Max+1; i<=36; i++)
{
int sum = 0;
for(int j=0; j<len; j++)
{
if(s[j]>='A' && s[j]<='Z')
{
sum = sum*i+(s[j]-'A'+10);
sum %= (i-1);
}
else
{
sum = sum*i+(s[j]-'0');
sum %= (i-1);
}
}
if(sum == 0)
{
cout<<i<<endl;
goto endW;
}
}
puts("No Solution");
endW:;
}
return 0;
}

波比源码 – 精品源码模版分享 | www.bobi11.com
1. 本站所有资源来源于用户上传和网络,如有侵权请邮件联系站长!
2. 分享目的仅供大家学习和交流,您必须在下载后24小时内删除!
3. 不得使用于非法商业用途,不得违反国家法律。否则后果自负!
4. 本站提供的源码、模板、插件等等其他资源,都不包含技术服务请大家谅解!
5. 如有链接无法下载、失效或广告,请联系管理员处理!
6. 本站资源售价只是赞助,收取费用仅维持本站的日常运营所需!
7. 如遇到加密压缩包,请使用WINRAR解压,如遇到无法解压的请联系管理员!

波比源码 » 51NOD 1116 K进制下的大数(字符串取模 + 枚举)

发表评论

Hi, 如果你对这款模板有疑问,可以跟我联系哦!

联系站长
赞助VIP 享更多特权,建议使用 QQ 登录
喜欢我嘛?喜欢就按“ctrl+D”收藏我吧!♡