Probability of Euler’s Totient Function in a range [L, R] to be divisible by M
source link: http://codeforces.com/blog/entry/105934
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
Sehwag has been solving a lot of mathematical problems recently. He was learning ETF (Euler Totient Function) and found the topic quite interesting. So, he tried solving a question on ETF. He will be given two numbers L and R. He has to find the probability that the ETF of a number in the range [L, R] is divisible by a number K.
hi guys! i have to solve this question and the only problem im facing rn are these
1 <= T <= 10
1 <= L <= R <= 10^12
0 <= R-L <= 10^5
1 <= K <= 10^6
cant fugure out how to do this in accordance with these constraints,can someone help me with it please?
|
16 minutes ago, # | Let's calculate φφ for all numbers in range using formula φ(n)=n∏p∣np−1pφ(n)=n∏p∣np−1p. But to do this we need to know factorizations of each number. Let's fix some kk, such that k2>Rk2>R, and let's denote N=R−LN=R−L. First, find all primes from 11 to kk using Eratosphenes sieve. Then, for each pp find all numbers in range [L,R][L,R] divisible by pp. It can be done in O(N/p)O(N/p) time, so in total O(N∑p⩽k1p)=O(Nloglogk)O(N∑p⩽k1p)=O(Nloglogk) according to Second Mertens Theorem(if you don't know this fact, you can say, that ∑p⩽k1p⩽∑n=1k1n=O(logk)∑p⩽k1p⩽∑n=1k1n=O(logk), it's enough in this case) After that, for each number nn from range [L,R][L,R] we know all prime divisors less than kk, and thus know factorization, because k2>Rk2>R. Knowing all factorizations, we can calculate φφ for all numbers and find how many of them divisible by kk, and thus calculate required probability. I'd say, that complexity is O(R1/2+NlogN)O(R1/2+NlogN), it may get some logarithmic factors depending on which sieve you're going to use, but it still must be enough. |
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK