转圈游戏 https://www.luogu.org/problemnew/show/P1965
比较容易想到的思路:
进行 10^k 轮游戏后的结果与进行 (10^k)%n 的结果是一致的, 所以只需要快速幂求 (10^k)%n, 然后再求出 (10^k)%n 轮后的结果即可.
快速幂时记得开 long long
- Code:
- #include <iostream>
- #include <cstdio>
- #include <cstring>
- #include <cmath>
- using namespace std;
- //Mystery_Sky
- //
- #define M 1000100
- #define ll long long
- ll n, m, k, x, ans;
- ll quickPow(ll x, ll k)
- {
- ll ret = 1;
- while(k) {
- if(k & 1) ret = (ret * x) % n;
- k>>= 1;
- x = (x * x) % n;
- }
- return ret % n;
- }
- int main() {
- ll t;
- scanf("%lld%lld%lld%lld", &n, &m, &k, &x);
- t = quickPow(10, k);
- for(int i = 1; i <= t; i++) {
- x = (x + m) % n;
- }
- printf("%lld\n", x);
- return 0;
- }
来源: http://www.bubuko.com/infodetail-3111512.html