11440 - Help Tomisu

All about problems in Volume 114. 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
zuluaga
New poster
Posts: 5
Joined: Sat Jan 05, 2008 9:17 pm

11440 - Help Tomisu

Post by zuluaga » Mon Mar 31, 2008 3:15 am

How to reduce the space?
Inclusion Exclusion, even precomputing is too slow.
product of primes go as high as ~O(n!).
Thanks.

pradhanp
New poster
Posts: 10
Joined: Mon Mar 31, 2008 2:14 am

Post by pradhanp » Mon Mar 31, 2008 3:57 am

You only need to report the answer modulo 100000007. So the product of primes being O(n!) does not matter.

Hint : Euler's totient function

mmonish
Experienced poster
Posts: 109
Joined: Sun Mar 11, 2007 2:55 pm
Location: SUST

Re: 11440 - Help Tomisu

Post by mmonish » Sat May 17, 2008 6:11 am

I tried to solve this prob but getting WA.
Anyone check my output for the following input
Input:

Code: Select all

2 1
9999 999
10000000 9900000
1000000 900000
5000 1999
10000000 9999999
100 1
10000 1
100000 9999
3 3
9999999 9899999
100000 100
7 1
11 11
11 5
33 20
0 0
My AC output:

Code: Select all

1
99851434
83058271
3985314
86471500
38637795
64325779
6388459
13359237
1
95631054
18032357
5039
8294399
10644479
20979144

mmonish
Experienced poster
Posts: 109
Joined: Sun Mar 11, 2007 2:55 pm
Location: SUST

Re: 11440 - Help Tomisu

Post by mmonish » Sat May 17, 2008 2:00 pm

Got AC.....
now the previous outputs r correct.

tobby
Learning poster
Posts: 98
Joined: Fri Dec 30, 2005 3:31 pm

Re: 11440 - Help Tomisu

Post by tobby » Thu May 22, 2008 11:39 am

Could anyone give some hints?

I only know that Answer = N! - 1 - (those with factors <= M), but I find no way to use this fact at all.

Maybe there is some way to compute the desired number directly? :-?

Robert Gerbicz
Experienced poster
Posts: 196
Joined: Wed May 02, 2007 10:12 pm
Location: Hungary, Pest county, Halasztelek
Contact:

Re: 11440 - Help Tomisu

Post by Robert Gerbicz » Thu May 22, 2008 1:52 pm

tobby wrote:Could anyone give some hints?
Euler's totient function+precomputation. And don't forget that: M<=N (without it, it would be much harder)

tobby
Learning poster
Posts: 98
Joined: Fri Dec 30, 2005 3:31 pm

Re: 11440 - Help Tomisu

Post by tobby » Thu May 22, 2008 8:10 pm

I guess I need a much bigger hint then....... :(

All numbers having every prime factors > M must be relative prime to M!. But how do we relate M and N? How do we use Euler phi here?

-- EDIT --

Oh I see - all numbers relatively prime to a number k can be written in the form N*k+v, where v<k and v,k are relatively prime.... I think I see the solution now. Thanks!

Wait.... I then have to find a way to compute phi(N!), where N <= 10^7?

Ah, phi(N!) = phi((N-1)!) * something... :D

calicratis19
Learning poster
Posts: 76
Joined: Mon Jul 21, 2008 8:50 am
Location: SUST,SYLHET,BANGLADESH.
Contact:

Re: 11440 - Help Tomisu

Post by calicratis19 » Fri May 22, 2009 7:10 am

cant understand how to use euler phi in this prob. can anyone pls explain... :oops: :oops: :oops:
Heal The World

roticv
Learning poster
Posts: 63
Joined: Sat Dec 11, 2004 9:28 am

Re: 11440 - Help Tomisu

Post by roticv » Tue May 26, 2009 4:50 pm

phi(N!) = number of numbers between 1 and N! which has no common factors with (1...N) ie number of numbers between 1 and N! with prime factors > N.

calicratis19
Learning poster
Posts: 76
Joined: Mon Jul 21, 2008 8:50 am
Location: SUST,SYLHET,BANGLADESH.
Contact:

Re: 11440 - Help Tomisu

Post by calicratis19 » Wed May 27, 2009 9:13 am

i got it :D :D :D . i wasnt properly understanding ur explanation first.maybe u should write with some more stops(.) and blank line :wink: :wink: :wink: . but i got it now :lol: :lol: :lol: .many many thx
Heal The World

Post Reply

Return to “Volume 114 (11400-11499)”