E-牛牛小数点_牛客练习赛89 (nowcoder.com)
题目描述
牛牛想和点点交朋友, 于是点点给了牛牛一个问题
数据范围
1 ⩽ T ⩽ 100 , 1 ⩽ l ⩽ r ⩽ 1 0 15
思路
证明
代码
#include<bits/stdc++.h> #include<unordered_map> #define int long long #define INF 0x3f3f3f3f #define INFL 0x3f3f3f3f3f3f3f3f #define mod 1000000007 #define MOD 998244353 #define rep(i, st, ed) for (int (i) = (st); (i) <= (ed);++(i)) #define pre(i, ed, st) for (int (i) = (ed); (i) >= (st);--(i)) #define debug(x,y) cerr << (x) << " == " << (y) << endl; using namespace std; typedef long long LL; typedef unsigned long long ULL; typedef pair<int, int> PII; template<typename T> inline T gcd(T a, T b) { return b ? gcd(b, a % b) : a; } template<typename T> inline T lowbit(T x) { return x & -x; } //template<typename T> T qmi(T a, T b = mod - 2, T p = mod) { T res = 1; b %= (p - 1 == 0 ? p : p - 1); while (b) { if (b & 1) { res = (LL)res * a % p; }b >>= 1; a = (LL)a * a % p; }return res % mod; } const int N = 1e5 + 10; int qmi(int a, int b) { int res = 1; while (b) { if (b & 1)res = (res * a); b >>= 1; a = (a * a); } return res; } int cal(int r) { int res = 0; int t2 = log(r) / log(2ll); for (int i = 0; i <= t2; ++i) { for (int j = 0; qmi(5ll, j) * qmi(2ll, i) <= r; ++j) { //debug("i", i); //debug("j", j); int x = r / (qmi(2ll, i) * qmi(5ll, j)); x = ((x - x / 2ll - x / 5ll + x / 10ll - 1ll) + MOD) % MOD; res = (res + (max(i, j) + 1ll) * x % MOD) % MOD; } } return res % MOD; } void solve() { int l, r; scanf("%lld%lld", &l, &r); cout << (cal(r) - cal(l - 1) + MOD) % MOD << endl; } signed main() { int _; cin >> _; while (_--) solve(); return 0; }
