11876  N + NOD (N)
Moderator: Board moderators

 New poster
 Posts: 9
 Joined: Sat Sep 11, 2010 1:21 am
 Location: Rio de Janeiro  Brasil
11876  N + NOD (N)
How to find de number of divisors of a number quickly? In brute force it will time lime. I thought to use sieve of Eratosthenes and then use the primes to determine the number of divisors, but i think it will time limite too.
Thanks.
Thanks.
Computer Science  UERJ  Rio de Janeiro  Brasil.
Re: 11876  N + NOD(N)
The method you described should work. However, you need to preprocess all the answers and give O(1) output for each case.

 New poster
 Posts: 9
 Joined: Sat Sep 11, 2010 1:21 am
 Location: Rio de Janeiro  Brasil
Re: 11876  N + NOD(N)
That was my idea. First generate in a vector all the possible numbers in the sequence (max 1000000), then only use iterators to get the numbers and give the distance. For a small sequence of number it works, my problem is to generate greater numbers because i have a "for from i=1 to n" and check if "n % 1 == 0". So it takes much time.sohel wrote:The method you described should work. However, you need to preprocess all the answers and give O(1) output for each case.
If you have any idea to get the numbers of divisors...
Thanks,
Ítalo.
Computer Science  UERJ  Rio de Janeiro  Brasil.
Re: 11876  N + NOD(N)
Hi " ItaloSpedini " This is very simple Number Theory Problem I sloved This problem this way :
1=> generate the divisor sequence
2=>from 1to 1000000 set a vector with 0 and 1
3=> cumulative sum of set vector
Then O(1) produce the output.
hope it help you.
1=> generate the divisor sequence
2=>from 1to 1000000 set a vector with 0 and 1
3=> cumulative sum of set vector
Then O(1) produce the output.
hope it help you.

 New poster
 Posts: 9
 Joined: Sat Sep 11, 2010 1:21 am
 Location: Rio de Janeiro  Brasil
Re: 11876  N + NOD(N)
I didn't understand. The divisor sequence will be the prime numbers? Then i create a set with 0 1 0 1 in each position?MRH wrote:Hi " ItaloSpedini " This is very simple Number Theory Problem I sloved This problem this way :
1=> generate the divisor sequence
2=>from 1to 1000000 set a vector with 0 and 1
3=> cumulative sum of set vector
Then O(1) produce the output.
hope it help you.
Thanks.
Computer Science  UERJ  Rio de Janeiro  Brasil.

 New poster
 Posts: 6
 Joined: Mon Jun 21, 2010 9:21 pm
Re: 11876  N + NOD(N)
@ItaloSpedini, did u solve the problem uva 294 called divisors? If u didn't then go to steven halim's site and try to find the number of total divisor of an integer that way using prime factorization. It's a bit tricky to do it within time limit but i think u can do it if u give the matter a deep thought. U can consult algorthmist too.
Make it a function and find all the numbers of the sequence. Keep the record in a boolean array or ur the way u want. Then follow MRH's way. If ur problem is how to do cumulative sum, for that u make a integer array. Set the 1st element to be zero. Then for 1 to 1000000, make a for loop and check like if the num is within the sequence then add 1 with the previous element if not it is equal to previous one. The O(1) process is like
no.of num in sequence= nod nod[a1] /* a and b are given ranges, a=<b */
Hope that helps if u didn't solve the problem yet.
Make it a function and find all the numbers of the sequence. Keep the record in a boolean array or ur the way u want. Then follow MRH's way. If ur problem is how to do cumulative sum, for that u make a integer array. Set the 1st element to be zero. Then for 1 to 1000000, make a for loop and check like if the num is within the sequence then add 1 with the previous element if not it is equal to previous one. The O(1) process is like
no.of num in sequence= nod nod[a1] /* a and b are given ranges, a=<b */
Hope that helps if u didn't solve the problem yet.

 New poster
 Posts: 9
 Joined: Sat Sep 11, 2010 1:21 am
 Location: Rio de Janeiro  Brasil
Re: 11876  N + NOD(N)
Bella Swan wrote:@ItaloSpedini, did u solve the problem uva 294 called divisors? If u didn't then go to steven halim's site and try to find the number of total divisor of an integer that way using prime factorization. It's a bit tricky to do it within time limit but i think u can do it if u give the matter a deep thought. U can consult algorthmist too.
Make it a function and find all the numbers of the sequence. Keep the record in a boolean array or ur the way u want. Then follow MRH's way. If ur problem is how to do cumulative sum, for that u make a integer array. Set the 1st element to be zero. Then for 1 to 1000000, make a for loop and check like if the num is within the sequence then add 1 with the previous element if not it is equal to previous one. The O(1) process is like
no.of num in sequence= nod nod[a1] /* a and b are given ranges, a=<b */
Hope that helps if u didn't solve the problem yet.
Thanks Bella Swan. I'll see the problem 294 and try to use your tips to pass the problem.
Thanks.
Computer Science  UERJ  Rio de Janeiro  Brasil.

 Learning poster
 Posts: 62
 Joined: Sat Nov 21, 2009 10:17 pm
 Location: CUET,Chittagong,Bangladesh
Re: 11876  N + NOD(N)
Can anyone give me more i\o?
If you have determination, you can do anything you want....

 New poster
 Posts: 6
 Joined: Mon Jun 21, 2010 9:21 pm
Re: 11876  N + NOD(N)
Hi, Naseef! there are 64725 numbers in this sequence. if you can find all of them, you can easily get accepted. here're some i/o from my ac code. hope it will help.
Code: Select all
Input:
5
1 1000000
1 5635
1 50000
58963 1000000
75698 321478
Output:
Case 1: 64725
Case 2: 619
Case 3: 4361
Case 4: 59717
Case 5: 16637
Input:
5
899 900
7 7
368 963
125 895
1147 11489
Output:
Case 1: 0
Case 2: 1
Case 3: 82
Case 4: 98
Case 5: 951
Last edited by Bella Swan on Wed Mar 30, 2011 6:12 pm, edited 1 time in total.

 New poster
 Posts: 12
 Joined: Wed Aug 18, 2010 12:07 pm
Re: 294Divisors WA please help me
Code: Select all
#include<stdio.h>
#include<math.h>
unsigned long int divisor(unsigned long int a)
{
unsigned long int i,count=0,tmp=sqrt(a);
//if(a==1)return 1;
for(i=1;i<=tmp;i++)
{
if(a%i==0)
count=count+2;
}
if(a==tmp*tmp)count=count;
return count;
}
int main()
{
unsigned long int n,i,count,tmp=0,ans,a,b,j;
scanf("%u",&n);
for(i=1;i<=n;i++)
{count=0;
scanf("%u%u",&a,&b);if(a>b) {j=a;a=b;b=j;}
for(j=a;j<=b;j++)
{
count=divisor(j);
if(tmp<count)
{
tmp=count;
ans=j;
}
}
printf("Between %u and %u, %u has a maximum of %u divisors.\n",a,b,ans,tmp);
}
return 0;
}