12005 - Find Solutions

[iriz7482]

I get TLE on this problem .

Code: Select all

#include<stdio.h>
#include<math.h>

main()
{
     long long n, i, j, k, r, t;
     while(1)
     {
         scanf("%lld",&n);
         if(!n) break;
         k = 4*n-3; i = 3; j = 2*n;
         r = 1;  t = sqrt(k);
         while(i <= t)
         { 
             if(j%i == 0)
             {
                  r++;
//              printf("%lld %lld\n",j/i,(i+1)/2);
             }
             i+=2; j++;
         }
         r*=2;
         if(r > 2 && t*t == k) r--;
         printf("%lld %lld\n",n,r);
     }
}

[ruet_std]

"The input file contains around 3000 line of input. Each line contains an integers n ( 0 < n<=10^14)."

Way too many input. Need a direct solution.

[iriz7482]

I solved it, no need to find solutions, just count them

[kanone]

i find all the prime till limit = sqrt(4N-3)
for(i=0;i<1270608 && prime<=limit;i++){
if(prime>N) break;
count=0;
while(N%prime==0){
count++;
N/=prime;
}
ans*=(count+1);
}
but it got TLE : (
plz help me : (

[saiful_islam]

AC

[brianfry713]

Yes count the number of divisors of 4*n-3.

[brianfry713]

Input:

Code: Select all

1020
400
1
10
100
1000
10000
100000
1000000
10000000
100000000
1000000000
10000000000
100000000000
1000000000000
10000000000000
100000000000000
0

AC output:

Code: Select all

1020 8
400 2
1 1
10 2
100 2
1000 4
10000 8
100000 8
1000000 4
10000000 16
100000000 8
1000000000 6
10000000000 8
100000000000 4
1000000000000 4
10000000000000 4
100000000000000 2

[brianfry713]

saiful_islam, don't use sqrt, try multiplying instead.

[triplemzim]

getting TLE ... please help me....

Code: Select all

#include<iostream>
#include<cstdio>




using namespace std;

int main()
{
    long long int c,a,b,last=0;

    scanf("%lld",&c);
    do
    {
        int count=0;
        a=4*c-3;
        if(a%2==0)
        {
            b=4;
            count=2;
            for(;b<=a/b;b++)
            {
                if(a%b==0) count++;
            }

            if((b-1)*(b-1)==a) count=count*2-1;
            else count = 2*count;
            cout<<c<<" "<<count+2<<endl;
        }
        else
        {
             for(b=3;b<=a/b;b=b+2)
             {
                if(a%b==0) count++;
             }

            if((b-2)*(b-2)==a) count=count*2-1;
            else count = 2*count;
            cout<<c<<" "<<count+2<<endl;
        }
        cin>>c;
    }while(c);
    return 0;
}

another method i tried :

Code: Select all

#include<stdio.h>
#include<math.h>

int main(){


    double a,b,c,s,last=0;
    long long ad;

    while(scanf("%lf",&c)==1)
    {
        if(c==0) break;
        int count=0;

        last=0; b=0;

       long long i=(sqrt(1-4*(1-c))+1)/2;


        for(b=2;b<=i;b++)
        {

            a=(2*c-2+b)/(2*b-1);
            ad=a;

            if(a==ad) count++;
        }

        if(c!=1) count=count*2+2;
       printf("%.0lf %d\n",c,count);

    }
return 0;
}

[brianfry713]

Precompute a list of primes.