ADDNDIV - Editorial

editorial
, , ,
42 
1
76 66

Correct answer is NO

1 Like
43

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
44

Thanks :relieved:

45 
#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  add push_back
#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

46

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

Edit:

Besides that: consider the test case:

1
24 6
47

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

48

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

2 Likes
49

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.

50

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

51

@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).

Thanks for the link though!

1 Like
52

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

53

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

54

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

55

#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?

56

pure dead brilliant darling

1 Like
57

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

1 Like
58

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
59

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
60

Thanks buddy!

2 Likes
61

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