QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#31637 | #2897. Circle Bounce | dccoku_sd | AC ✓ | 3ms | 3720kb | C++ | 988b | 2022-05-10 20:45:47 | 2022-05-10 20:45:48 |
Judging History
answer
#include <iostream>
using namespace std ;
using ll = long long ;
const ll MOD = 1000000007 ;
ll expo(ll a, ll n, ll MOD) {
n %= (MOD-1) ;
ll r = 1 ;
while (n) {
if (n & 1)
r = (r * a) % MOD ;
a = (a * a) % MOD ;
n >>= 1 ;
}
return r ;
}
ll inv(ll a, ll MOD) {
a %= MOD ;
return expo(a, MOD-2, MOD) ;
}
int main() {
ll a, b, n ;
cin >> a >> b >> n ;
ll r = (a*a-b*b) % MOD ;
ll s = (a*a+b*b) % MOD ;
ll t = 2*a*b % MOD ;
ll x = -1 ;
ll y = 0 ;
ll z = 1 ;
n++ ;
while (n != 0) {
if (n & 1) {
ll x2 = (x*r-y*t) % MOD ;
ll y2 = (x*t+y*r) % MOD ;
z = z*s % MOD ;
x = x2 ;
y = y2 ;
}
ll r2 = (r*r-t*t) % MOD ;
ll t2 = (2*r*t) % MOD ;
s = s*s % MOD ;
r = r2 ;
t = t2 ;
n >>= 1 ;
}
ll res = x * inv(z, MOD) % MOD ;
res = (res + MOD) % MOD ;
cout << res << endl ;
}
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 3520kb
input:
999999998 999999999 1000000000
output:
86174826
result:
ok single line: '86174826'
Test #2:
score: 0
Accepted
time: 1ms
memory: 3720kb
input:
314159265 1414213 31413413
output:
174644643
result:
ok single line: '174644643'
Test #3:
score: 0
Accepted
time: 3ms
memory: 3680kb
input:
355 113 1000000000000
output:
964036762
result:
ok single line: '964036762'
Test #4:
score: 0
Accepted
time: 0ms
memory: 3716kb
input:
267204667 335545842 696754506694
output:
869642485
result:
ok single line: '869642485'
Test #5:
score: 0
Accepted
time: 3ms
memory: 3568kb
input:
608585399 831320119 672380354760
output:
16481017
result:
ok single line: '16481017'
Test #6:
score: 0
Accepted
time: 1ms
memory: 3668kb
input:
376844222 336360777 909739767563
output:
610206681
result:
ok single line: '610206681'
Test #7:
score: 0
Accepted
time: 3ms
memory: 3584kb
input:
812478595 209900954 868059762327
output:
396736907
result:
ok single line: '396736907'
Test #8:
score: 0
Accepted
time: 3ms
memory: 3572kb
input:
508794642 851378491 104036237152
output:
843802314
result:
ok single line: '843802314'
Test #9:
score: 0
Accepted
time: 3ms
memory: 3568kb
input:
1 1 3
output:
1000000006
result:
ok single line: '1000000006'
Test #10:
score: 0
Accepted
time: 2ms
memory: 3592kb
input:
1 2 1
output:
960000007
result:
ok single line: '960000007'
Test #11:
score: 0
Accepted
time: 2ms
memory: 3452kb
input:
11 63 44
output:
22
result:
ok single line: '22'
Test #12:
score: 0
Accepted
time: 1ms
memory: 3656kb
input:
163 713 980
output:
0
result:
ok single line: '0'