1116?K進制下的大數?

基準時間限制：1?秒 空間限制：131072?KB 分值:?20?難度：3級算法題

?收藏

?關注

有一個字符串S，記錄了一個大數，但不知這個大數是多少進制的，只知道這個數在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

正如一個數能被9整除的充要條件是各位置上的數字之和被9整除一樣，K進制下的數能被K-1整除的充要條件是各個位置上的數字之和能被K-1整除。。。

#include<bits/stdc++.h> #include<stdio.h> #include<iostream> #include<cmath> #include<math.h> #include<queue> #include<set> #include<map> #include<iomanip> #include<algorithm> #include<stack> #define inf 0x3f3f3f3f typedef long long ll; namespace IO {const int MT = 10 * 1024 * 1024; /// 10MB 請注意輸入數據的大小！！！char IO_BUF[MT];int IO_PTR, IO_SZ;/// 要記得把這一行添加到main函數第一行！！！void begin() {IO_PTR = 0;IO_SZ = fread (IO_BUF, 1, MT, stdin);}template<typename T>inline bool scan_d (T & t) {while (IO_PTR < IO_SZ && IO_BUF[IO_PTR] != '-' && (IO_BUF[IO_PTR] < '0' || IO_BUF[IO_PTR] > '9'))IO_PTR ++;if (IO_PTR >= IO_SZ) return false;bool sgn = false;if (IO_BUF[IO_PTR] == '-') sgn = true, IO_PTR ++;for (t = 0; IO_PTR < IO_SZ && '0' <= IO_BUF[IO_PTR] && IO_BUF[IO_PTR] <= '9'; IO_PTR ++)t = t * 10 + IO_BUF[IO_PTR] - '0';if (sgn) t = -t;return true;}inline bool scan_s (char s[]) {while (IO_PTR < IO_SZ && (IO_BUF[IO_PTR] == ' ' || IO_BUF[IO_PTR] == '\n') ) IO_PTR ++;if (IO_PTR >= IO_SZ) return false;int len = 0;while (IO_PTR < IO_SZ && IO_BUF[IO_PTR] != ' ' && IO_BUF[IO_PTR] != '\n')s[len ++] = IO_BUF[IO_PTR], IO_PTR ++;s[len] = '\0';return true;}template<typename T>void print(T x) {static char s[33], *s1; s1 = s;if (!x) *s1++ = '0';if (x < 0) putchar('-'), x = -x;while(x) *s1++ = (x % 10 + '0'), x /= 10;while(s1-- != s) putchar(*s1);}template<typename T>void println(T x) {print(x); putchar('\n');} }; using namespace IO; using namespace std; char s[1000050]; int n,w=0; int digit(char c){if('0'<=c&&c<='9')return c-'0';return c-'A'+10; } int main(){begin();scan_s(s);int len=strlen(s);for(int i=0;i<len;++i){n+=digit(s[i]);w=max(w,digit(s[i]));}for(int i=w;i<36;++i)if(n%i==0){printf("%d\n",i+1);return 0;}printf("No Solution\n"); }

?

轉載于:https://www.cnblogs.com/linruier/p/9747089.html

總結

以上是生活随笔為你收集整理的51 Nod 1116 K进制下的大数的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。