QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#31637#2897. Circle Bouncedccoku_sdAC ✓3ms3720kbC++988b2022-05-10 20:45:472022-05-10 20:45:48

Judging History

This is the latest submission verdict.

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-05-10 20:45:48]
  • Judged
  • Verdict: AC
  • Time: 3ms
  • Memory: 3720kb
  • [2022-05-10 20:45:47]
  • Submitted

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 ;
}

Details

Tip: Click on the bar to expand more detailed information

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'