11440  Help Tomisu
Moderator: Board moderators
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.
Inclusion Exclusion, even precomputing is too slow.
product of primes go as high as ~O(n!).
Thanks.
Re: 11440  Help Tomisu
I tried to solve this prob but getting WA.
Anyone check my output for the following input
Input:
My AC output:
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
Code: Select all
1
99851434
83058271
3985314
86471500
38637795
64325779
6388459
13359237
1
95631054
18032357
5039
8294399
10644479
20979144
Re: 11440  Help Tomisu
Got AC.....
now the previous outputs r correct.
now the previous outputs r correct.
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?
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?

 Experienced poster
 Posts: 196
 Joined: Wed May 02, 2007 10:12 pm
 Location: Hungary, Pest county, Halasztelek
 Contact:
Re: 11440  Help Tomisu
Euler's totient function+precomputation. And don't forget that: M<=N (without it, it would be much harder)tobby wrote:Could anyone give some hints?
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((N1)!) * something...
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((N1)!) * something...

 Learning poster
 Posts: 76
 Joined: Mon Jul 21, 2008 8:50 am
 Location: SUST,SYLHET,BANGLADESH.
 Contact:
Re: 11440  Help Tomisu
cant understand how to use euler phi in this prob. can anyone pls explain...
Heal The World
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.

 Learning poster
 Posts: 76
 Joined: Mon Jul 21, 2008 8:50 am
 Location: SUST,SYLHET,BANGLADESH.
 Contact:
Re: 11440  Help Tomisu
i got it . i wasnt properly understanding ur explanation first.maybe u should write with some more stops(.) and blank line . but i got it now .many many thx
Heal The World