11876 - N + NOD (N)

All about problems in Volume 118. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

Post Reply
ItaloSpedini
New poster
Posts: 9
Joined: Sat Sep 11, 2010 1:21 am
Location: Rio de Janeiro - Brasil

11876 - N + NOD (N)

Post by ItaloSpedini » Tue Nov 16, 2010 3:21 am

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.
Computer Science - UERJ - Rio de Janeiro - Brasil.

User avatar
sohel
Guru
Posts: 856
Joined: Thu Jan 30, 2003 5:50 am
Location: New York

Re: 11876 - N + NOD(N)

Post by sohel » Tue Nov 16, 2010 6:14 am

The method you described should work. However, you need to pre-process all the answers and give O(1) output for each case.

ItaloSpedini
New poster
Posts: 9
Joined: Sat Sep 11, 2010 1:21 am
Location: Rio de Janeiro - Brasil

Re: 11876 - N + NOD(N)

Post by ItaloSpedini » Tue Nov 16, 2010 6:06 pm

sohel wrote:The method you described should work. However, you need to pre-process all the answers and give O(1) output for each case.
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.

If you have any idea to get the numbers of divisors...

Thanks,
Ítalo.
Computer Science - UERJ - Rio de Janeiro - Brasil.

MRH
Learning poster
Posts: 51
Joined: Mon Aug 11, 2008 9:09 pm

Re: 11876 - N + NOD(N)

Post by MRH » Tue Nov 16, 2010 6:13 pm

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.

ItaloSpedini
New poster
Posts: 9
Joined: Sat Sep 11, 2010 1:21 am
Location: Rio de Janeiro - Brasil

Re: 11876 - N + NOD(N)

Post by ItaloSpedini » Wed Nov 17, 2010 1:44 am

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.
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?

Thanks.
Computer Science - UERJ - Rio de Janeiro - Brasil.

Bella Swan
New poster
Posts: 6
Joined: Mon Jun 21, 2010 9:21 pm

Re: 11876 - N + NOD(N)

Post by Bella Swan » Sat Nov 27, 2010 10:55 pm

@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[a-1] /* a and b are given ranges, a=<b */

Hope that helps if u didn't solve the problem yet.

ItaloSpedini
New poster
Posts: 9
Joined: Sat Sep 11, 2010 1:21 am
Location: Rio de Janeiro - Brasil

Re: 11876 - N + NOD(N)

Post by ItaloSpedini » Sun Nov 28, 2010 8:00 pm

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[a-1] /* 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.

naseef_07cuet
Learning poster
Posts: 62
Joined: Sat Nov 21, 2009 10:17 pm
Location: CUET,Chittagong,Bangladesh

Re: 11876 - N + NOD(N)

Post by naseef_07cuet » Wed Dec 01, 2010 1:12 pm

Can anyone give me more i\o?
If you have determination, you can do anything you want....:)

Bella Swan
New poster
Posts: 6
Joined: Mon Jun 21, 2010 9:21 pm

Re: 11876 - N + NOD(N)

Post by Bella Swan » Thu Dec 02, 2010 9:41 am

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.

Mizanur Rahman(IUK)
New poster
Posts: 12
Joined: Wed Aug 18, 2010 12:07 pm

Re: 294-Divisors WA please help me

Post by Mizanur Rahman(IUK) » Tue Dec 07, 2010 5:41 pm

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

Post Reply

Return to “Volume 118 (11800-11899)”