Kn0wthyself's blog

By Kn0wthyself, history, 7 weeks ago, In English

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.

  • Vote: I like it
  • -7
  • Vote: I do not like it

»
7 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

just number of divisors of gcd

Spoiler
  • »
    »
    7 weeks ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    This will give you TLE

    #include<bits/stdc++.h>
    using namespace std;
    
    void solve(int a){
        int c=0;
        for(int i=1;i<sqrt(a);i++){
                if(a%i==0){
                    if(a/i==i)c++;
                    else c+=2;
                }
        }
        cout<<c<<endl;
    }
    int gcd(int a,int b)
    {
    	if(a==0)
    		return b;
    	return gcd(b%a,a);
    }
    int main(){
        int t;
        cin>>t;
        while(t--){
            int l,m;
            cin>>l>>m;
            int a=gcd(l,m);
            solve(a);
        }
    }
    
    • »
      »
      »
      7 weeks ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

      yeah because that's sqrt(1e6) * 1e6 = 1e9

      learn sieve of eratosthenes

      • »
        »
        »
        »
        7 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Oh! Thanks! I didn’t think that way. My pleasure for your instruction.

      • »
        »
        »
        »
        7 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        But i have a question why this this solution excepted

        #include <stdio.h>
        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<t;j++)
        	{
        		int a,b,cd=0;
        		scanf("%d%d",&a,&b);
        		int n = gcd(a,b);
        		for(int i=1;i*i<=n;i++)
        		{
        			if(n%i==0)
        			{
        				if(n/i==i)
        					cd+=1;
        				else
        					cd+=2;
        			}
        		}
        		printf("%lld\n",cd);
        	}
        	return 0;
        }
        
        • »
          »
          »
          »
          »
          7 weeks ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          luck? dunno, there's still a simple solution that passes comfortably.