### Kn0wthyself's blog

By Kn0wthyself, history, 5 months ago,

Today I am share my new experience . I am trying to solve a problem in SPOJ. Problem link:https://www.spoj.com/problems/COMDIV/ When I solve this problem using C++ it gives TLE for simple code. For this problem my solving approach was at first find the GCD of two values than from 1 to GCD I use a loop if any number is divided by that than i count it for two time without corner case. But it gives me Time Limited Exceed. I really become astonished to see this. Than just i convert it into c . instead of cin use scanf and instead of cout use printf than it accept the code. Truly it was a bad experience for me in problem solving.

• -7

 » 5 months ago, # |   0 just number of divisors of gcd Spoiler/** * author: phares * created: at some point **/ #include using namespace std; #ifdef LOCAL #include "algo/debug.h" #else #define debug(...) 42 #endif int main() { ios::sync_with_stdio(false); cin.tie(0); int tt = 1;; cin >> tt;; vector cnt(int(1e6 + 1)); for (int i = 1; i <= int(1e6); i++) { for (int j = i; j <= int(1e6); j += i) { cnt[j]++; } } while (tt--) { int a, b; cin >> a >> b; cout << cnt[__gcd(a, b)] << '\n'; } return 0; } 
•  » » 5 months ago, # ^ | ← Rev. 2 →   0 This will give you TLE #include using namespace std; void solve(int a){ int c=0; for(int i=1;i>t; while(t--){ int l,m; cin>>l>>m; int a=gcd(l,m); solve(a); } } 
•  » » » 5 months ago, # ^ |   +3 yeah because that's sqrt(1e6) * 1e6 = 1e9learn sieve of eratosthenes
•  » » » » 5 months ago, # ^ |   0 Oh! Thanks! I didn’t think that way. My pleasure for your instruction.
•  » » » » 5 months ago, # ^ |   0 But i have a question why this this solution excepted #include int gcd(int a,int b) { if(a==0) return b; return gcd(b%a,a); } int main(void) { int t; scanf("%d",&t); for(int j=0;j
•  » » » » » 5 months ago, # ^ |   0 luck? dunno, there's still a simple solution that passes comfortably.