Coolguys getting TLE

coolguys
tle

#1

In the problem cool guys : http://www.codechef.com/problems/COOLGUYS/
I am getting TLE , how do I make this code fast enough??

    #include<stdio.h>

long long int getgcd(int a,int b){
if(b==0)
    return a;
 return getgcd(b,a%b);
}

void func(long long int n){
long long int i,j,x,gcd,count=0;
for(i=1;i<=n;i++){
    for(j=1;j<=i;j++){
            if(i%j==0)
            count++;
    }
}
x=n*n;
gcd = getgcd(count,x);
printf("%lld/%lld

",count/gcd,x/gcd);
}

int main(){
int t;
long long int n;
scanf("%lld",&t);
while(t--){
    scanf("%lld",&n);
    func(n);
}
return 0;
}

#2

In the func function, it seems you have implemented an O(n^2) algorithm. Now look at the constraints for the problem. 1 <= N <= 10^9.

This means there must exist at least an O(n) solution to the problem.

If case you do not understand complexity notation, O(n) means looping only n times instead of n^2 times (O(n^2), as you were doing in your func function). Look for a simpler solution than this.