首页 > 代码库 > ural 1104，暴力取模
ural 1104，暴力取模
题目链接：http://acm.timus.ru/problem.aspx?space=1&num=1104
题目大意：输入一个字符串（数字与大写字母组成），输出n，n满足此字符串为n进制时，其n进位制数能被n-1整除（n不存在时输出"No solution"(不包括双引号)）。
题目好多坑点，我也是WA了好几次才A的。算法是暴力的。
1，刚开始，我怎么都想不清楚，答案就是2啊，任何数都可以被1整除啊，其实，不是这样的，比如说，123就不是2进制数，所以说，这里要找到字符串中最大的字符，从maxnum+1进制开始找。
2，test 6,就是在%(k-1)，可能除以了0，就是说你要找最大的maxnum = 1;这时就不对了，应该将maxnum和2比较一下。
#include <bits/stdc++.h>using namespace std;#define maxn 1000100char str[maxn];long long num[maxn];int len;int getnum(char a){ if(a>=‘0‘&&a<=‘9‘) return (a-‘0‘); else return (a-‘A‘+10);}bool judge(int k){ //long long base = 1; long long sum = 0; /* for(int i=len-1; i>=0; i--) { sum +=num[i]*base; base*=k; } if(sum%(k-1)==0) return true; return false; */ for(int i=len-1;i>=0;i--) { sum +=num[i]; sum = sum%(k-1); sum*=k; } return sum==0;}int main(){ scanf("%s",str); len = strlen(str); int maxnum = 0; for(int i = 0; i<len; i++) { num[i] = getnum(str[i]); if(maxnum<num[i]) maxnum = num[i]; } int k; bool flag = false; if(maxnum<2) k = 2; else k = maxnum+1; for(; k<=36; k++) { if(judge(k)) { flag = true; break; } } if(flag) printf("%d\n",k); else puts("No solution."); return 0;}
ural 1104，暴力取模
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。