Cool Subsets COOLSBST SOLUTION Code Chef

Cool Subsets COOLSBST SOLUTION Code Chef

An integer XX is cool if it has a primitive root modulo XX.

The coolness of a non-empty set of NN distinct integers S={x1,x2,…,xN}S={x1,x2,…,xN} is the number of cool divisors of ∏Ni=1xi∏i=1Nxi.

You are given four integers LL, RR, AA and BB. Let SS be the set containing all integers between LL and RR (inclusive). Consider all non-empty subsets of SS with size between AA and BB (inclusive). Find the sum of values of coolness of all these subsets. Since this sum can be huge, compute it modulo 998,244,353998,244,353.


  • The first line of the input contains a single integer TT denoting the number of test cases. The description of TT test cases follows.
  • The first and only line of each test case contains four space-separated integers LL, RR, AA and BB.


For each test case, print a single line containing one integer ― the total coolness modulo 998,244,353998,244,353.


  • 1≤T≤100,0001≤T≤100,000
  • 1≤L≤R≤100,0001≤L≤R≤100,000
  • 1≤A≤B≤100,0001≤A≤B≤100,000


Subtask #1 (10 points):

  • R≤16R≤16
  • B≤16B≤16

Subtask #2 (35 points): A=BA=B

Subtask #3 (55 points): original constraints

Example Input

3 4 1 2
1 10 15 20
1 8 1 8

Example Output



Example case 1: We have S = {3,4}{3,4}, which has the following 33 non-empty subsets with sizes in the range [1,2][1,2]:

  • {3}{3}: coolness 22, the cool divisors are {1,3}{1,3}
  • {4}{4}: coolness 33, the cool divisors are {1,2,4}{1,2,4}
  • {3,4}{3,4}: coolness 55, the cool divisors are {1,2,3,4,6}{1,2,3,4,6}

Example case 2: There are no subsets with size in the range [15,20][15,20], so the sum is 00.


January Long Challenge 2021

Leave a Comment