GCD

[alcatraz98]

Write your question here.
Whats problem in my code

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

[Thomas1965]

Whats problem in my code

Maybe you can tell us.
Compiler error, wrong output, crash....

[ih7MizwU]

i can give gcdmod code in exchange of kcompression code

[tpb]

Besides the excessive complexity and small errors the overall approach simply won't work. Consider:

             Factors
a=9699690    2 3 5 7 11 13 17 19
b=   5187      3   7    13    19
n=2

Calculating the gcd without the modulus on the power:

GCD(9699690^2+5187^2,9699690-5187)
=GCD(94083986096100+26904969,9694503)
=GCD(94084013001069,9694503)
=108927  ( = 5187 * 21 )

But if we first take 94084013001069 % 1000000007 = 12342481 and do the GCD with that we get a different answer:

GCD(12342481,9694503)
=1

[Manga]

Well I notice the use of a string variable without #include <string>.

[tpb]

@Manga, In gcc <iostream> indirectly includes <string>:

<iostream>
  <ostream>
    <ios>
      <bits/ios_base.h>
        <system_error>
          <stdexcept>
            <string>

Of course you should always include <string> anyway if you're using strings. But g++ won't complain if you forget it (but have included <iostream>).

The whole string part of his code is pointless, though, since the mod-power has already "reduced" the integers.

His code boils down to something like this.

#include <iostream>

using INT = long long;
const INT MOD = 1000000007;

INT gcd(INT a, INT b) {
    while (b != 0) { INT t = b; b = a % b; a = t; }
    return a;
}

INT power(INT x, INT y, INT p = MOD) {
    INT res = 1;      
    x %= p;  
    while (y > 0) {
        if (y & 1) res = (res * x) % p;
        y >>= 1; 
        x = (x * x) % p;  
    }
    return res;
}

int main() {
    int t;
    std::cin >> t;
    while (t--) {
        INT a, b, n;
        std::cin >> a >> b >> n;
        INT powsum = (power(a, n) + power(b, n)) % MOD;
        std::cout << gcd(powsum, std::abs(a - b)) << '\n';
    }
}