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 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78
|
#include<iostream>
#include<vector>
#include<math.h>
#include<algorithm>
using namespace std;
long long int gcd( long long int a , long long int b){
if(!a)
return b;
return gcd(b%a , a);
}
long long int reduce(long long int second , string first){
long long int mod = 0;
for(long long int i = 0 ; i < first.length() ; i++){
mod = (mod*10 + first[i] - '0')%second;
}
return mod ;
}
long long int gcdLarge(string first , long long int second){
long long int num = reduce(second , first);
return gcd(second , num);
}
long long int power(long long int x, long long int y, long long int p = 1000000007)
{
long long int res = 1;
x = x % p;
while (y > 0)
{
if (y & 1)
res = (res*x) % p;
y = y>>1;
x = (x*x) % p;
}
return res;
}
int main()
{
int t;
cin>>t;
while(t--){
long long int a , b , n;
cin>>a>>b>>n;
string first = to_string(power(a , n) + power(b , n)%(1000000007));
long long int second = abs(a-b);
if(a == b){
cout<<(power(a , n)%(1000000007) + power(b , n)%(1000000007))%(1000000007)<<endl;
}
else{
cout<<gcdLarge(first , second)<<endl;
}
}
return 0;
}
| |