E - Equal Digits Gym - 100519E（数学）

本文主要是介绍E - Equal Digits Gym - 100519E（数学），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

For the given integer N and digit D, find the minimal integer K ≥ 2 such that the representation of N in the positional numeral system with base K contains the maximum possible consecutive number of digits D at the end.

Input
The input contains two integers N and D (0 ≤ N ≤ 1015, 0 ≤ D ≤ 9).

Output
Output two integers: K, the answer to the problem, and R, the the number of consecutive digits D at the end of the representation of N in the positional numeral system with base K.

Examples
Input
3 1
Output
2 2
Input
29 9
Output
10 1
Input
0 4
Output
2 0
Input
90 1
Output
89 2

题意：
给一个数字$n$。要求其在K进制下，末尾为D的连续数目最多，求K和连续数目R。

思路：
也不算特别数学吧。
$n$的范围到了$1e15$。但是很明显，如果要使得$R\ge 3$，K一定要小于$sqrt(n)$。这一部分可以$for$出来。而对于$R\le 2$的部分，你可以直接算出来！

也就是，直接令n减去D（n≥D)，那么就得到R=1。
如果$(n-D)\mathrm{m}\mathrm{o}\mathrm{d}D==0$ $(D!=0)$,那么就得到R=2。

注意当n=0,D=0的时候，答案是2,1。需要考虑的情况还是挺多的，博主就卡了这道题挺久。

#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <set>
#include <queue>
#include <map>
#include <string>
#include <iostream>
#include <cmath>using namespace std;
typedef long long ll;const ll maxn = 3e7 + 4e6;ll N;
int D;int cal(int K) {int cnt = 0;ll x = N;while(x) {ll num = x % K;if(num == D) {cnt++;}else {return cnt;}x /= K;}return cnt;
}int main() {scanf("%lld%d",&N,&D);if(N == 0 && D == 0) {printf("2 1");return 0;}int mi = 0;ll pos = 2;for(int K = 2;K <= maxn;K++) {int num = cal(K);if(num > mi) {mi = num;pos = K;}}if(mi <= 2 && N >= maxn) {ll x = N;x -= D;if(mi < 1) {mi = 1;pos = x;}if(D != 0 && x % D == 0) {if(mi < 2) {mi = 2;pos = x / D;}}}printf("%lld %d\n",pos,mi);return 0;
}

这篇关于E - Equal Digits Gym - 100519E（数学）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---