【nowcoder 225284】牛牛小数点(结论)(数学)

牛牛小数点

题目链接:nowcoder 225284

到牛客看:

——>点我跳转<——

题目大意

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

思路

首先丢出两个结论:(其实比赛的时候推一推猜一猜都能有)
如果 x x x 质因子分解之后只有 2 , 5 2,5 2,5,那它就是不循环的。(这个显然)

然后如果 x x x 是循环的,它的循环节开始维护就是 1 + max ⁡ { n u m 2 , n u m 5 } 1+\max\{num_2,num_5\} 1+max{ num2,num5}。( n u m i num_i numi 是质因数分解 x x x 之后 i i i 这个质数的个数)

这里给一下网上看到的玄学证明:
如果没有 2 , 5 2,5 2,5 因子,通过一个叫做欧拉降幂的东西可以知道 1 0 i ≡ 1 (   m o d     x ) 10^i\equiv1(\bmod\ x) 10i1(mod x) 是一定有解的。
那也就说,存在 i , j i,j i,j 使得 x j = 1 0 i − 1 xj=10^i-1 xj=10i1,然后通分 x = 1 0 i − 1 j x=\dfrac{10^i-1}{j} x=j10i1
然后有 1 x = j 1 0 i − 1 \dfrac{1}{x}=\dfrac{j}{10^i-1} x1=10i1j,然后就会得出这是一个循环节长度为 i i i,内容为 j j j 的无限循环小数。
这里个人感觉十分玄学,但事实就是如此。
那如果没有 2 , 5 2,5 2,5,循环就是从 1 1 1 开始。

而有 2 , 5 2,5 2,5 的情况,我们就乘 max ⁡ { n u m 2 , n u m 5 } \max\{num_2,num_5\} max{ num2,num5} 10 10 10,这样它可能分子不是 1 1 1,但我们看到影响循环节长度(以及开始位置)的是 i i i 啊,跟它无关。
那这个时候你得到的就是从 1 1 1 开始,那把 10 10 10 除回去就是从 1 + max ⁡ { n u m 2 , n u m 5 } 1+\max\{num_2,num_5\} 1+max{ num2,num5} 开始的。

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

那一共有 ⌊ n 2 i 5 j ⌋ \left\lfloor\dfrac{n}{2^i5^j}\right\rfloor 2i5jn 个可能的数。
为什么是可能呢?因为你规定了 2 , 5 2,5 2,5 个数,那你选的 x x x 2 i 5 j 2^i5^j 2i5j 之后不能有 2 , 5 2,5 2,5 因子。

那要怎么找因子呢?
那我们就是要找没有 2 , 5 2,5 2,5 因子的数,那我们考虑这些数有什么特点。
(其实可以直接容斥一下得到,但我比赛的时候不是用容斥的)
如果有 2 2 2 的因子,那它末尾肯定是 0 , 2 , 4 , 6 , 8 0,2,4,6,8 0,2,4,6,8 其中一个,如果有 5 5 5 的因子,那它末尾肯定是 0 , 5 0,5 0,5 其中一个。
那我们就需要统计有多少个数的末尾不是这些,也就是在 1 , 3 , 7 , 9 1,3,7,9 1,3,7,9 之中。

然后大于 10 10 10 的部分直接 x / 10 ∗ 4 x/10*4 x/104,小于的直接暴力判断。

然后就好啦。

代码

#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;
}
    原文作者:SSL_TJH
    原文地址: https://blog.csdn.net/weixin_43346722/article/details/120518181
    本文转自网络文章,转载此文章仅为分享知识,如有侵权,请联系博主进行删除。
点赞