Page 1 of 1
12005 - Find Solutions
Posted: Tue Jun 07, 2011 7:51 am
by 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);
}
}
Re: 12005 - Find Solutions
Posted: Thu Aug 11, 2011 10:08 am
by 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.
Re: 12005 - Find Solutions
Posted: Fri Sep 02, 2011 3:36 pm
by iriz7482
I solved it, no need to find solutions, just count them
Re: 12005 - Find Solutions
Posted: Fri Jan 20, 2012 9:27 am
by 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 : (
Re: 12005 - Find Solutions verdict WA :( plz see my steps
Posted: Fri Mar 30, 2012 10:21 pm
by saiful_islam
AC
Re: 12005 - Find Solutions
Posted: Tue Apr 03, 2012 1:00 am
by brianfry713
Yes count the number of divisors of 4*n-3.
Re: 12005 - Find Solutions
Posted: Thu Apr 05, 2012 9:56 pm
by 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
Re: 12005 - Find Solutions
Posted: Thu Apr 05, 2012 10:37 pm
by brianfry713
saiful_islam, don't use sqrt, try multiplying instead.
Re: 12005 - Find Solutions
Posted: Mon May 20, 2013 12:50 am
by 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;
}
Re: 12005 - Find Solutions
Posted: Tue May 21, 2013 3:45 am
by brianfry713
Precompute a list of primes.