视频链接 https://www.nowcoder.com/study/vod/1041/3/1
(数学)
java党太难了,没有过竞赛经历,求各位大佬轻喷
时间复杂度
参考文献
java 代码
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int T = in.nextInt();
for (int iCase = 1; iCase <= T; iCase++) {
long F = in.nextLong();
long L = in.nextLong();
System.out.println("Case #" + iCase +": " + (getNoNineCount(L) - getNoNineCount(F) + 1));
}
}
private static long getNoNineCount(long N) {
long res = 0;
String str = Long.toString(N);
int length = str.length();
for (int i = 0; i < length - 1; i++) {
res += (str.charAt(i) - '0') * myPow(9, length - i - 2) * 8;
}
for (long i = N - N % 10; i <= N; i++) {
if (i % 9 != 0) {
res ++;
}
}
return res;
}
public static long myPow(long x, int n) {
long out = 1;
for (int i = n; i != 0; i = i / 2) {
if (i % 2 != 0)
out *= x;
x = x * x;
}
return out;
}
}