Hint1
对于将长字符串转换为数值并取模的问题，在许多编程语言中，例如 int 或 long long 类型，都无法存储如此大的数字。那么，有没有一种简单的方法来解决这个问题呢？
Hint2
字符串S需要循环多少次才能得出答案呢？是否有一个上限可以参考，以防止程序运行超时？
Solution
我们知道 12345 % 10 = 5，让我们从另一面来看待它。
首先，考虑每一位数字的逐步处理：
- 初始时，结果为 0。
- 处理第一个字符 '1'： (0∗10+1)%10=1
- 处理第二个字符 '2'： (1∗10+2)%10=2
- 处理第三个字符 '3'： (2∗10+3)%10=3
- 处理第四个字符 '4'： (3∗10+4)%10=4
- 处理第五个字符 '5'： (4∗10+5)%10=5
经过 5 次循环，答案为 5。你是否发现了规律？
每次处理一个字符时，我们将当前结果乘以 10，再加上该字符对应的数字，然后对模数取模。这保证了每一步的结果都在模数范围内，避免了大数运算的溢出问题。
现在我们已经解决了大数对小数取模的问题，但我们还不清楚 字符串 循环次数的上界。为了解决这个问题，我们需要了解抽屉原理。
抽屉原理（也称鸽巢原理）简单来说是：如果 个物体放入 个抽屉，而 ，那么至少有一个抽屉包含多个物体。例如4个球放进3个抽屉，必然有一个抽屉至少2个球，这很好理解，但在我们的问题中，应用起来可能不太直观。
在这个问题中，一种直观的想法是采用暴力尝试的方法。具体来说，我们可以循环字符串S 次，每次将循环后的字符串转化为数值对 取模，会得到一个结果 。如果 为0，就输出循环了多少次。但我们并不知道循环次数的上界。根据抽屉原理，我们知道 mod 的结果范围在 0 到 之间，即有 个抽屉。因此，如果有 个球，至少有一个抽屉会包含两个球。基于此，我们可以暴力遍历 次，如果在 次内找到了答案就直接结束，否则输出 -1，因为 次循环必定会出现重复的情况。而一旦出现重复，后续的 , 等都会重复，因此没有必要继续循环，以免超时。
c语言代码
#include <stdio.h>
#include <stdlib.h>
int main() {
int x, s, res = 0, cnt = 0;
scanf("%d%d",&x,&s);
for (int i = 1; i <= x; i++) {//抽屉原理 x后面的不用循环,必然会重复,1-x是一个循环周期
cnt++;
res = (1000 * res + s) % x;//长字符串逐步取模,*1000是因为字符串S长度为3
if (res == 0) {
printf("%d\n",cnt);
return 0;
}
}
printf("-1\n");
return 0;
}
c++代码
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define inf 0x3f3f3f3f3f3f3f3f
typedef pair<int, int> PII;
void solve() {
int x, s, res = 0, cnt = 0;
cin >> x >> s;
for (int i = 1; i <= x; i++) {//抽屉原理 x后面的不用循环,必然会重复,1-x是一个循环周期
cnt++;
res = (1000 * res + s) % x;//长字符串逐步取模,*1000是因为字符串S长度为3
if (res == 0) {
cout << cnt << endl;
return;
}
}
cout << -1 << endl;
}
signed main() {
int t = 1;
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
// cin>>t;
while (t--) solve();
return 0;
}