Thanks! Was informative and would be a nice addition to anybody’s repertoire of debugging.
1 Like
In complexity analysis of the editorial:
The number of prime factors in the factorisation of a is \le \log a
I can’t seem to reason why. Can somebody please explain why?
Say any number N is made of K primes so we can say that
N=p_1^{\alpha_1} \times p_2^{\alpha_2} \dots p_K^{\alpha_K} \\
since \alpha_i \ge 1 \ \forall \ 1 \le i \le K
N \ge p_1\times p_2\times p_3 \dots p_K
Also any prime p_i \ge2
\implies N \ge 2^K \\
\boxed{\therefore \log N \ge K}
4 Likes
I don’t know what is happening.
Same solution gave TLE in contest (TLE solution) and now giving accepted (Accepted)
You can check. The code is exact same.
I was trying to upsolve by looking at others solution and found that some of them got accepted with the similar solution -
For example - accepted 1
accepted2
Can anyone give me any reason for that??
Funny Edit : Same solution is giving TLE in 2 test cases now - HAHAHAHA
could you pls tell me, why i’m getting WA, I checked for every prime factor!!
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 
1
6 2
3 Likes
Maybe the flag simply doesn’t work with u128int 
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.
Why you break when x*x > a in your code . Can you plz explain ?