Hard Compare — Exponential
source link: http://codeforces.com/blog/entry/88878
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
How to arrive at the correct solution which solves for large input values?
Problem : Hard Compare...
Question
Given 4 numbers A,B,C and D. If AB > CD, print "YES" otherwise, print "NO".
Input
Only one line containing 4 numbers A,B,C and D (1≤A,C≤107) , (1≤B,D≤1012)
Output
Print "YES" or "NO" according to the problem above.
My Program
#include <iostream>
#define ll long long
using namespace std;
int main(){
ll res1, res2, a, b, c, d;
cin>>a>>b>>c>>d;
res1 = 1;
res2 = 1;
for(int i=1;i<=b; i++){
res1 = a % ((int)1e9+7) * res1 % ((int)1e9+7);
}
for(int i=1;i<=d; i++){
res2 = c % ((int)1e9+7) * res2 % ((int)1e9+7);
}
cout<<(res1>res2 ? "YES" : "NO");
return 0;
}
TestCases
Input : 2887969 614604076030 8478041 209676100616
Answer : YES
Input : 8376260 70 8376259 70
Answer : YES
Input : 2 1 1 1
Answer : YES
Input : 1 7816997 1 1
Answer : NO
Issue with current program : I am not able to solve for large input values
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK