给定$n<=10^{12}$询问$\sum_{x=1}^n \sum_{y=1}^n \left[ \dfrac{x}{y}\text{是有限小数}\right]$
做法
当真分数$\dfrac {x}{y}$中分母y为$2^p5^q$的形式时才为有限小数即可以表示成$\dfrac {d*gcd(x, y)}{2^p5^qgcd(x,y)}$考虑枚举分母y，则可行的x的个数为$\left \lfloor \dfrac {n}{\zeta(y)} \right\rfloor$，$\zeta(y)$表示小于等于y的最大的不含2和5的因子的整数，相当于是gcd(x, y)这样是O(n)的，考虑改变枚举顺序枚举$\zeta(y)$，那么答案就是$\sum_{k=1}^n [2 \nmid k][5\nmid k] \left \lfloor \dfrac {n}{k} \right \rfloor g(\left \lfloor \dfrac{n}{k} \right \rfloor)$显然可以整除分块，其中g(i)代表小于等于i的且能表示成$2^p5^q$的数的个数（相当于是贡献次数）。然后可以通过容斥计算出区间内不被2和5整除的数的个数。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
| #include <bits/stdc++.h>
#define mp make_pair
#define pb push_back
#define sz(x) (int)x.size()
#define all(x) begin(x), end(x)
#define fi first
#define se second
#define debug(x) cerr << #x << " " << x << '\n'
using namespace std;
using ll = long long;
using pii = pair<int,int>;
using pli = pair<ll,int>;
const int INF = 0x3f3f3f3f, N = 2e5 + 5;
const ll LINF = 1e18 + 5;
constexpr int mod = 1e9 + 7;
ll n;
ll f(ll x)
{
return x - x/2 - x/5 + x/10;
}
ll g(ll x)
{
ll ans = 0;
for(ll i=1; i<=x; i*=2)
{
for(ll j=1; j<=x; j*=5)
{
if(i*j>x) break;
ans++;
}
}
return ans;
}
int main()
{
scanf("%lld", &n);
ll ans = 0;
for(ll l=1,r; l<=n; l=r+1)
{
r = min(n, n/(n/l));
ans += (f(r) - f(l-1))*(n/l)*g(n/l);
}
printf("%lld\n", ans);
return 0;
}
|