題目鏈接 Problem Description As we know, Rikka is poor at math. Yuta is worrying about this situation, so he gives Rikka some math tasks to practice. Ther ...
Problem Description As we know, Rikka is poor at math. Yuta is worrying about this situation, so he gives Rikka some math tasks to practice. There is one of them:
In radix d, a number K=(A1A2...Am)d(Ai∈[0,d),A1≠0) is good if and only A1−Am is a permutation of numbers from 0 to d−1.
A number K is good if and only if there exists at least one d≥2 and K is good under radix d.
Now, Yuta wants to calculate the number of good numbers in interval [L,R]
It is too difficult for Rikka. Can you help her?
Input The first line contains a number t(1≤t≤20), the number of the testcases.
For each testcase, the first line contains two decimal numbers L,R(1≤L≤R≤105000).
Output For each testcase, print a single line with a single number -- the answer modulo 998244353.
Sample Input 2 5 20 123456 123456789 Sample Output 3 114480 題意： 一個數 x 如果用 d 進位進行表示，是0~d-1的一個排列（不能以0打頭），那麼這個數稱為 “優數”，一個數只要存在任意一個 d 進位符合0~d-1的一個排列，那麼就是“優數”,問L到R區間有多少個優數？ 思路：按進位計算，找邊界，一定存在dl和dr是邊界，dl+1~dr-1 進位的所有排列都在L~R之間。 代碼如下：
import java.math.BigInteger; import java.util.Scanner; public class Main { static int MAXN = 1600; static BigInteger[] dx = new BigInteger[MAXN]; static long MOD = 998244353; static long [] fac = new long [MAXN]; static void Init(){ dx[0] = BigInteger.ZERO; dx[1] = BigInteger.ZERO; for(int i=2; i<MAXN; i++){ dx[i] = BigInteger.ZERO; for(int j=i-1; j>=0; j--){ dx[i] = dx[i].multiply(BigInteger.valueOf(i)).add(BigInteger.valueOf(j)); } } fac[0] = fac[1] = 1; for(int i=2; i<MAXN; i++) fac[i]=fac[i-1]*i%MOD; } static int Low(BigInteger x){ int low=0, high=MAXN-1; while(low < high){ int mid = (low+high)/2; if(dx[mid].compareTo(x)>=0)high = mid; else low = mid+1; } return high; } public static void main(String[] args){ Init(); Scanner in = new Scanner(System.in); int T = in.nextInt(); for(int cas=1; cas<=T; cas++){ int [] vis = new int [MAXN]; for(int i=0; i<MAXN; i++) vis[i] = 0; BigInteger L, R; L = in.nextBigInteger(); R = in.nextBigInteger(); int dl = 0, dr = 0; dl = Low(L)+1; dr = Low(R)-1; long ans = fac[dr]-fac[dl-1]; ans = (ans%MOD+MOD)%MOD; if(dl > dr) ans = 0; dl--; dr++; long ans2=0; BigInteger tmp = (BigInteger.valueOf(dl)).pow(dl-1); for(int i=dl; i>=1; i--){ int top = L.divide(tmp).intValue(); if(i==dl && top==0) { ans2 = (ans2+fac[dl]-fac[dl-1])%MOD; break; } int cnt=0; for(int o=top+1;o<dl;o++) if(vis[o]==0) cnt++; ans2 = (ans2+(cnt)*fac[i-1]%MOD)%MOD; if(vis[top] == 1) break; L = L.mod(tmp); if(i==1 && vis[top]==0) ans2=ans2+1; vis[top] = 1; tmp = tmp.divide(BigInteger.valueOf(dl)); } long ans1 = 0; for(int i=0; i<MAXN; i++) vis[i] = 0; tmp = (BigInteger.valueOf(dr)).pow(dr-1); for(int i=dr; i>=1; i--) { int top = R.divide(tmp).intValue(); if(i==dr && top==0) {ans1 = (ans1+fac[dr]-fac[dr-1]%MOD); break;} int cnt=0; for(int o=top+1;o<dr;o++) if(vis[o]==0) cnt++; ans1 = (ans1+(cnt)*fac[i-1]%MOD)%MOD; if(vis[top] == 1) break; R = R.mod(tmp); vis[top] = 1; tmp = tmp.divide(BigInteger.valueOf(dr)); } // System.out.println("ans1 -> "+ans1); // System.out.println("ans2 -> "+ans2); // System.out.println("ans -> "+ans); // System.out.println("DL -> "+dl); // System.out.println("DR -> "+dr); ans = ans+ans2 + fac[dr]-fac[dr-1]-ans1; if(dl==dr) ans=ans2-ans1; ans = (ans%MOD+MOD)%MOD; System.out.println(ans); } } }
