正题

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

题目大意

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

\[\sum_{i=l}^rf(i)
\]

\(1\leq T\leq 100,1\leq l\leq r\leq 10^{15}\)

解题思路

设\(a_i\)表示\(i\)位之后的余数，那么出现循环节当且仅当\(a_i\)出现重复。

\[a_i=a_{i-1}\times 10\% n\Rightarrow a_i=10^i\%n
\]

那么出现循环节一定满足存在一个正整数\(k\)使得

\[a_i\times 10^k\equiv a_i(mod\ n)
\]

\[\Rightarrow 10^k\equiv 1(mod\ \frac{n}{gcd(a_i,n)})
\]

我们知道\(10^k\equiv 1(mod\ n)\)有解当且仅当\(gcd(10,n)=1\)。

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

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

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

时间复杂度：\(O(T\log_2n\log_5 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;

}

巴特西

牛客练习赛89E-牛牛小数点【数论】

正题

题目大意

解题思路

code

最新文章

热门文章