UnlLucky_Girl's blog

Need help in this Number Theory Problem
By UnlLucky_Girl, history, 5 years ago, In English

Give me idea for the following problem.

The positive divisor function is defined as a function that counts the number of positive divisors of an integer N, including 1 and N. If we define the positive divisor function as D(N), then, for example: D(24) = 8 (Because 24 has 8 divisors and they are 1, 2, 3, 4, 6, 8, 12, 24) Calculating D(N) is a classical problem and there are many efficient algorithms for that. But what if you are asked to find something different? Given a range and an integer K, can you find out for how many N in the given range, D(N) equals K?

Input:

In the very first line, you’ll have an integer called T. This is the number of test cases that shall follow. Every test case contains three integers, L, R, and K. L and R represent the range and are inclusive.

Constraints:

● 1 ≤ T < 31

● 1 ≤ L ≤ R < 2^31

● 1 ≤ K < 2^31

Output:

For every test case, you must print the case number, followed by the count of numbers with exactly K divisors in the range.

  • Vote: I like it
  • +2
  • Vote: I do not like it

Comments Comments (4)
| Write comment?
»
5 years ago, # |
  Vote: I like it +1 Vote: I do not like it

Auto comment: topic has been updated by UnlLucky_Girl (previous revision, new revision, compare).

→ Reply
»
5 years ago, # |
← Rev. 2   Vote: I like it +1 Vote: I do not like it

This is the problem E from MIST NCPC Contest 2020. Had you read the editorial of the contest?

→ Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

i saw a problem like this in timus online judge, and it was saying that find the minimum number that has the most divisors. and here is my code

ll Ans = 1, ANS = 1, n;

vector < ll > P;

void BT(ll ind = 0, ll limit = 60, ll cu = 1, ll cnt = 1) { if(cu > n || ind >= 14)return; if(Ans < cnt) { ANS = cu; } else if(Ans == cnt) { ANS = min(ANS, cu); } Ans = max(Ans, cnt); ll v = P[ind], PW = 1; for(ll i = 0; i <= limit; i++) { ll z = INF; ld C = cu; if(C * PW <= INF2) { z = cu * PW; } else { return; } BT(ind + 1, i, z, cnt * (i + 1)); PW *= v; if(PW > INF)return; PW = min(PW, INF); } }

int solve(){ //cout << fixed << setprecision(15); //scanf("%d %d %f %lld %s %c", &x); //printf("%d %d %f %lld %s %c", x); Ans = 1, ANS = 1; cin >> n; P = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47}; BT(); cout << ANS << " " << Ans << endl; return 0; } its a backtrack solution and its time complexity is good(i dont know the exact complexity) and for your problem you can just change a little part and it will be the solution :)

→ Reply