ADDNDIV - Editorial

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:

#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

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