书海扬帆的博客

提高组的数论题。

这道题目我自行思考并在十分钟内写出了正解,一种成就感油然而生。思路就是GCD/LCM再加上快速幂,反复根据同余取模。

学小学奥数的时候做这类周期问题做多了。。。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <cstring>
using namespace std;
typedef long long ll;
ll n,m,k,x;
ll gcd(ll a,ll b){
if(b==0) return a;
return gcd(b,a%b);
}
ll lcm(ll a,ll b){
ll now=gcd(a,b);
return (a/now)*(b/now)*now;
}
ll qmi(ll a,ll n,ll p){
ll m1=a,m2=n,ans=1;
while(n){
if(n%2) ans=(ans*a)%p;
a=(a*a)%p;
n/=2;
}
return ans;
}
int main(){
cin>>n>>m>>k>>x;
k=qmi(10,k,lcm(n,m));
k=(k*m)%n;
cout<<(x+k)%n<<endl;
return 0;
}



本站使用 Material-X 作为主题 , 总访问量为 次 。
载入天数...载入时分秒... 字数统计:730.1k