Informatics Olympiad all in one 1617: circle game | 1875: [13noip improvement group] circle game | Luogu p1965 [noip2013 improvement group] circle game

【 Topic link 】

ybt 1617： Circle game
ybt 1875：【13NOIP Improvement group 】 Circle game
Luogu P1965 [NOIP2013 Improvement group ] Circle game

【 Topic test site 】

1. Modulus operation

【 Their thinking 】

The first x After the first round, little buddy No. 1 went to $x+m$ Location , Come after the second round $x+2m$ Location , If the value of this position exceeds n, The position number should be reduced n, Make the position number only in 0~n-1 Within the scope of . therefore $10^k$ After wheel , The first x The location of little partner No. is $(x+10^k\cdot m)\%n$.
It is known that x、m All less than n. According to the multiplication application of congruence theorem ：$a\cdot b\%m=(a\%m\cdot b\%m)\%m$
Yes ：
$(x+10^k\cdot m)\%n$
$=(x\%n+(10^k\%n\cdot m\%n)\%n)\%n$
$=(x+(10^k\%n\cdot m)\%n)\%n$
The main problem is to seek $10^k\%n$
k achieve $10^9$, A fast power algorithm must be used here （ The complexity of fast power algorithm is $O(logn)$,n Is the size of the index ）.
According to the congruence Theorem , Yes ：$a^b\%m=(a\%m{)}^b$. In the process of using fast power , For the base number a And result r, After every operation, it's right m Take the mold .

【 Solution code 】

solution 1： Fast power

#include<bits/stdc++.h>
using namespace std;
int fastPowMod(int a, int b, int m)// Fast exponentiation a^b%m
{
    	
	int r = 1;// result 
	while(b > 0)
	{
    
		if(b % 2 == 1)
			r = (r * a) % m;
		a = (a * a) % m;
		b /= 2;
	} 
	return r;
}
int main()
{
    
	int n, m, k, x;
	cin >> n >> m >> k >> x;
	cout << (x + fastPowMod(10, k, n) * m % n) % n;
	return 0;
}