ADDNDIV - Editorial

Can anyone help me with my submission ?? Submission
What I tried to do is that I just go over all the powers of b such that b is less than 1e17 and checked everytime, whether a is perfectly dividing b or not.
Maybe it’s wrong because of Overflow, but I tried this and it didn’t gave me Runtime Error.
Thank You.

I have tried O(sqrt(a)) giving TLE
for 1sec sqrt(10^9) shouldnt give TLE right?

#include<bits/stdc++.h>
using namespace std;
int main()
{
int t;
cin>>t;
while(t–)
{
int a,b;
cin>>a>>b;
int x = 2;
bool f = true;
while(x<=sqrt(a))
{
if(a%x == 0)
{
a=a/x;
if(b%x !=0 )
{
f=false;
break;
}
}
else x++;
}
if(a>2 && b%a !=0) f = false;
if(!f) cout<<“NO\n”;
else cout<<“YES\n”;
}
return 0;
}

this is also i have tried many times
but in this solution i dont think anything is wrong
https://www.codechef.com/viewsolution/51680500
this is my solution

Thanks , can you please provide some test case where my code fails. My approach is , i calculate all the prime factors of a and checking them against b , if b % prime_fact != 0 for any prime factor , the ans will be NO else YES.

void solve()
{

    int a,b;
    scc(a)
    scc(b)

    bool ok = 0;
    for(int i=0;i<=50;i++)
    {
        if(bigmod(b,i,a) == 0) ok = 1;
    }
    if(ok)puts("YES");
    else puts("NO");

}

Is this the correct solution?
It got ac.

Interesting: it’s trivial to make this overflow: Add and Divide - Can some tell where it fails? - #2 by ssjgz

Can you link to your submission that uses the “check for overflow” trick?

2 Likes

i think i understood what is wrong with our approach
suppose we have b=1e9 and their exist an a for which b raised to power 4 or 5 is divisible
then b power 5 will overflow even unsinged long long int
so that’s that our approach dosen’t work for larger numbers

Yes, the logic is correct.

Given constraints, a \leq 10^9 so the highest power of any prime in a can be \log _2 a \leq 30. So you just need to check till maximum b^{30} if a ~ | ~ b.

Although you implementation is very repetitive, it works.

1 Like

Therefore, I Created this Post.

@admin, Please Do Take Up Feature of 12 Hr Hacking [Similar to CodeForces], That Would Really Improve the Test Cases, in case Tester has Missed it Out.

2 Likes

I am sorry earlier I tried this overflow trick but it gave Wrong answer.
Now I tried the same but using long long and it gave Runtime Error.
Thanks.
But I tried this problem using u128int (just to see what will happen) and used that same overflow trick, but that code gave me Wrong Answer, instead of Runtime Error.Link
Any reason why it didn’t gave Runtime Error?

1 Like

Glaring issue in this one - if you indented your code properly, you’d probably spot it straight away :slight_smile:

1                                                       
6 2
3 Likes

Maybe the flag simply doesn’t work with u128int :frowning:

2 Likes

You have to optimize it more since your code’s complexity is O(sqrt(n) * T) => in the worst case scenario, you code will have ~1e9 iterations which i guess will give TLE.

Oh i see , thanks a lot @ssjgz , will keep this in mind.

1 Like

Why you break when x*x > a in your code . Can you plz explain ?

The trapv flag only checks for signed overflows, but you are using an unsigned 128-bit type. Also the loop condition prevents it from overflowing because your limit is way too low. You can change “while(b1 <= (u128)1e20)” to “while(b1 * temp > b1)”, so that the loop will run until the eventual overflow and stop there. This may even give you an AC verdict. Changing to a signed 128-bit type will get it trapped by trapv and cause Runtime Error.

Edit: Actually this kind of solution would need a non-existing uint1024_t data type or some sort of a bigint class to avoid WA (a possible TLE depending on the input data is another story):

2 Likes

Thanks it worked for my solution.

1 Like
1
76 66

Correct answer is NO

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 :relieved: