## 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

zuluaga
New poster
Posts: 5
Joined: Sat Jan 05, 2008 9:17 pm

### 11440 - Help Tomisu

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

New poster
Posts: 10
Joined: Mon Mar 31, 2008 2:14 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

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

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

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

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

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

calicratis19
Learning poster
Posts: 76
Joined: Mon Jul 21, 2008 8:50 am
Contact:

### Re: 11440 - Help Tomisu

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

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

### Re: 11440 - Help Tomisu

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