牛牛小数点

题目链接：nowcoder 225284

到主站看：https://blog.csdn.net/weixin_43346722/article/details/120518181

题目大意

定义一个函数 f(i) 为 1/i 循环节从小数点后第几位开始，位数作为函数的结果。
如果是不循环的小数，那 f(i)=0。
然后要你求 f(1)~f(n) 的和。

思路

首先丢出两个结论：（其实比赛的时候推一推猜一猜都能有）
如果 质因子分解之后只有 ，那它就是不循环的。（这个显然）

然后如果 是循环的，它的循环节开始维护就是 。（ 是质因数分解 之后 这个质数的个数）

这里给一下网上看到的玄学证明：
如果没有 因子，通过一个叫做欧拉降幂的东西可以知道 是一定有解的。
那也就说，存在 使得 ，然后通分 。
然后有 ，然后就会得出这是一个循环节长度为 ，内容为 的无限循环小数。
这里个人感觉十分玄学，但事实就是如此。
那如果没有 ，循环就是从 开始。

而有 的情况，我们就乘 个 ，这样它可能分子不是 ，但我们看到影响循环节长度（以及开始位置）的是 啊，跟它无关。
那这个时候你得到的就是从 开始，那把 除回去就是从 开始的。

然后你考虑怎么快速求，考虑根据上面的性质，你枚举数质因数分解之后 的个数。
然后你考虑有多少个这样的数，设 个数分别为 。

那一共有 个可能的数。
为什么是可能呢？因为你规定了 个数，那你选的 除 之后不能有 因子。

那要怎么找因子呢？
那我们就是要找没有 因子的数，那我们考虑这些数有什么特点。
（其实可以直接容斥一下得到，但我比赛的时候不是用容斥的）
如果有 的因子，那它末尾肯定是 其中一个，如果有 的因子，那它末尾肯定是 其中一个。
那我们就需要统计有多少个数的末尾不是这些，也就是在 之中。

然后大于 的部分直接 ，小于的直接暴力判断。

然后就好啦。

代码

#include<map>
#include<queue>
#include<cstdio>
#include<vector>
#include<cstring>
#include<iostream>
#include<algorithm>
#define ll long long
#define mo 998244353

using namespace std;

int T;
ll l, r;

ll clac(ll x) {//统计有循环小数的个数
    ll re = x / 10 * 4;
    x %= 10;
    if (x >= 1) re++;
    if (x >= 3) re++;
    if (x >= 7) re++;
    if (x >= 9) re++;
    return re;
}

ll work(ll x) {//数位DP
    ll now = 1, pre, re = 0;
    ll xnm = 0, ynm = 0;
    while (now <= x) {
        pre = now;
        ynm = 0;
        while (now <= x) {
            ll maxn = x / now;
            re = (re + max(xnm + 1, ynm + 1) * (clac(maxn) - 1ll) % mo) % mo;

            ynm++;
            now *= 5ll;
        }
        xnm++;
        now = pre;
        now <<= 1;
    }
    return re;
}

int main() {
    scanf("%d", &T);
    while (T--) {
        scanf("%lld %lld", &l, &r);
        printf("%lld\n", ((work(r) - work(l - 1)) % mo + mo) % mo);
    }

    return 0;
}