## 12005 - Find Solutions

Moderator: Board moderators

iriz7482
New poster
Posts: 15
Joined: Mon Apr 04, 2011 3:18 pm

### 12005 - Find Solutions

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
New poster
Posts: 1
Joined: Thu Aug 11, 2011 10:01 am

### Re: 12005 - Find Solutions

"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
New poster
Posts: 15
Joined: Mon Apr 04, 2011 3:18 pm

### Re: 12005 - Find Solutions

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

kanone
New poster
Posts: 1
Joined: Fri Jan 20, 2012 9:08 am

### Re: 12005 - Find Solutions

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
New poster
Posts: 6
Joined: Tue Feb 08, 2011 7:41 pm

### Re: 12005 - Find Solutions verdict WA :( plz see my steps

AC
Last edited by saiful_islam on Fri Apr 06, 2012 5:16 pm, edited 2 times in total.

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

### Re: 12005 - Find Solutions

Yes count the number of divisors of 4*n-3.
Check input and AC output for thousands of problems on uDebug!

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

### Re: 12005 - Find Solutions

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``````
Check input and AC output for thousands of problems on uDebug!

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

### Re: 12005 - Find Solutions

saiful_islam, don't use sqrt, try multiplying instead.
Check input and AC output for thousands of problems on uDebug!

triplemzim
New poster
Posts: 48
Joined: Sat Apr 06, 2013 6:02 pm

### Re: 12005 - Find Solutions

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;

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);

}

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

}
return 0;
}
``````

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

### Re: 12005 - Find Solutions

Precompute a list of primes.
Check input and AC output for thousands of problems on uDebug!