1
76 66


1 Like

There can be at most one prime factor of N which is greater than \sqrt N, rest all will be be less than \sqrt N

2 Likes

Thanks

#include<bits/stdc++.h>
#include <unordered_map>
#include <vector>
#define int long long
#define w(x) int x; cin>>x; while(x--)
int mod = (int)1e9+7;
#define maxv 2147483647
#define minv -2147483648
#define MAX (int)1e7+7
using namespace std;
int GCD(int a,int b)
{
//  cout<<a<<" "<<b<<endl;
if(a%b==0)
{
return b;
}
return GCD(b,a%b);
}

void solve()
{
int x,y;
cin>>x>>y;
int k=GCD(max(x,y),min(x,y));
int z=x/k;
if(y%z==0)
{
cout<<"Yes\n";
return;
}
cout<<"No\n";
}
/* FOR STRINGS WHOLE LINE INPUT UISNG
string s;
getline(cin,s);
*/
/* IF AMOUNT OF DATA IS UNKNOWN THEN
while(cin>>x)
{
// CODE
}
*/
/* RANGE OF INT
-2 power 31 to 2 power 31 -1
RANGE OF LONG LONG
power 63
*/
// x=(x+m)%m;
// to compare double
/* if(abs(a-b)<1e-9)
{
equal
}
*/
int32_t main()
{
#ifndef ONLINE_JUDGE
freopen("Input.txt", "r", stdin);
freopen("Output.txt", "w", stdout);
#endif
ios_base::sync_with_stdio(0);
cin.tie(0);
pre();
int t;
cin >> t;
while (t--)
{
solve();
}
}



Can anyone give me a failing test case

This doesn’t seem to compile, as pre is not defined anywhere.

Edit:

Besides that: consider the test case:

1
24 6


I did a O(1) solution for this problem and even O(sqrt(N)) are being accepted!!!.
my solution-
https://www.codechef.com/viewsolution/51686598

More precisely log(log(N)). By Hardy-Ramanujan Theorem

2 Likes

Nice editorial. I had tried solving it with the Naive approach but failed quite a few times. I had figured out the math behind it but failed to code it properly, only until 5 minutes before the end of the contest.

Why my answer gives TLE, i guess my code is similar to that in Video Editorial? Pls let me know.

@shreyasshetty7 The Hardy Ramanujan Theorem you shared is in normal order. I would much rather estimate a worst case complexity than go by the average case complexity, which can fail for the outliers of the normal order estimation (howsoever small in numbers they might be). So, Ω(# of Prime Factors of a) = log(log(n)) while O(# of Prime Factors of a) = log(n).

1 Like

Yes understood that shortly after. From first look it did look like O(1) xD. Thanks btw!!

i don’t know bro i was also doing like that only but it was giving WA.if you understood why it was wrong please tell me bro

Your approach is find power of b which is divisible by a? then in that case the power if b can exceed 1e18. That’s why you got WA. i did same thing in python taking upto b^29 and got AC anything more than 29 would give TLE less than 29 would give WA

https://www.codechef.com/viewsolution/51752679

#include <bits/stdc++.h>
using namespace std;

int main() {
int T;
cin>>T;
while(T–)
{
int a,b;
bool ans=false;
cin>>a>>b;
for(int i=2;i<a;i++)
{
if(a%i==0)
{
if(b%i==0)
{
ans=true;
break;
}
}
}
if(ans)
cout<<“YES”<<endl;
else
cout<<“NO”<<endl;

}
return 0;


}

it’s getting TLE,can someone suggest?

1 Like

Thanks for telling me that O(log(a)) is actually O(1).

1 Like

One of the reasons your code is slow is because in your while condition (x <= sqrt(a)), the sqrt of a is being calculated again and again, which is slow. You can significantly speed it up by using the condition (x*x <= a). Let me know if that works because my worst case O(sqrt(n)) soln passed.

1 Like

I think the test cases are weak here, why do I say this? because I checked the prime factors till 1e5 only and still it got accepted, i.e if there would be a = prime number > 1e6 and b = the same prime number, my code would WA but it is not :p, though I submitted a modified version please look into it

1 Like

Thanks buddy!

2 Likes

Ohh!!! yarr thank you very much
it worked!!