正题

题目链接:https://ac.nowcoder.com/acm/contest/11179/E

---

题目大意

定义 f ( x ) f(x) f(x)表示 1 x \frac{1}{x} x1​的混循环节长度（如果没有循环节就是 0 0 0）， T T T组询问给出 l , r l,r l,r求
∑ i = l r f ( i ) \sum_{i=l}^rf(i) i=l∑r​f(i)

1 ≤ T ≤ 100 , 1 ≤ l ≤ r ≤ 1 0 15 1\leq T\leq 100,1\leq l\leq r\leq 10^{15} 1≤T≤100,1≤l≤r≤1015

---

解题思路

设 a i a_i ai​表示 i i i位之后的余数，那么出现循环节当且仅当 a i a_i ai​出现重复。
a i = a i − 1 × 10 % n ⇒ a i = 1 0 i % n a_i=a_{i-1}\times 10\% n\Rightarrow a_i=10^i\%n ai​=ai−1​×10%n⇒ai​=10i%n
那么出现循环节一定满足存在一个正整数 k k k使得
a i × 1 0 k ≡ a i ( m o d   n ) a_i\times 10^k\equiv a_i(mod\ n) ai​×10k≡ai​(mod n)
⇒ 1 0 k ≡ 1 ( m o d   n g c d ( a i , n ) ) \Rightarrow 10^k\equiv 1(mod\ \frac{n}{gcd(a_i,n)}) ⇒10k≡1(mod gcd(ai​,n)n​)
我们知道 1 0 k ≡ 1 ( m o d   n ) 10^k\equiv 1(mod\ n) 10k≡1(mod n)有解当且仅当 g c d ( 10 , n ) = 1 gcd(10,n)=1 gcd(10,n)=1。

也就是说我们要找到第一个 i i i使得 g c d ( 10 , n g c d ( a i , n ) ) = 1 gcd(10,\frac{n}{gcd(a_i,n)})=1 gcd(10,gcd(ai​,n)n​)=1。

而 a i a_i ai​每次乘十，所以相当于 n n n每次在质因数中去掉一个 2 2 2和 5 5 5，直到和 10 10 10互质。

但是这样还没有结束，因为如果没有循环节就是 0 0 0，而这里则会统计小数的长度，得减去这些情况，不难发现有循环节的话当且仅当存在某个 1 0 k % n = 0 10^k\%n=0 10k%n=0，也就是说 n n n只由 2 2 2和 5 5 5构成，暴力枚举这些数就好了。

时间复杂度： O ( T log ⁡ 2 n log ⁡ 5 n ) O(T\log_2n\log_5 n) O(Tlog2​nlog5​n)

---

code

#include<cstdio>
#include<cstring>
#include<algorithm>
#define ll long long
using namespace std;
const ll P=998244353;
ll T,l,r;
int Ask(ll n){
    ll ans=n;
    for(ll i=1,pw=2;pw<=n;i++,pw=pw*2ll)ans=(ans+n/pw)%P;
    for(ll i=1,pw=5;pw<=n;i++,pw=pw*5ll)ans=(ans+n/pw)%P;
    for(ll i=1,pw=10;pw<=n;i++,pw=pw*10ll)ans=(ans-n/pw)%P;
    for(ll i=1,pw=1;pw<=n;i++,pw=pw*2ll)
        for(ll j=1,qw=1;pw*qw<=n;j++,qw=qw*5ll)
            (ans-=max(i,j))%=P;
    return (ans+P)%P;
}
signed main()
{
    scanf("%lld",&T);
    while(T--){
        scanf("%lld%lld",&l,&r);
        printf("%lld\n",(Ask(r)-Ask(l-1)+P)%P);
    }
    return 0;
}