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.
Auto comment: topic has been updated by UnlLucky_Girl (previous revision, new revision, compare).
This is the problem E from MIST NCPC Contest 2020. Had you read the editorial of the contest?
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 :)
Thanks