回首过去

1 题目简述

题目：给定正整数 $n$ ( $1 \le n \le 10^{12}$ )，求出有序整数对 $(x,y)$ 的个数，满足 $1\le x,y\le n$ 且 $\frac{x}{y}$ 可以表示为十进制有限小数。

核心难点：数据规模高达 $10^{12}$ ，普通的 $O(n)$ 暴力枚举显然会超时，我们需要推导出一个 $O(\sqrt{n})$ 或更优的数论解法。

2 数学推导

有限小数的性质

首先，我们需要知道：一个最简分数 $\frac{A}{B}$ 能化为有限小数，当且仅当分母 $B$ 的质因子只包含 2 和 5。

根据上面的性质,我们写了一个最朴素的暴力枚举

代码1

点击

cpp

//非常暴力的算法
#include <bits/stdc++.h>
using namespace std;



//是否 y只有因子2 和 5
bool is_only_25(int y) {
    while( y % 2 == 0) y /=2;
    while( y % 5 == 0) y /=5;
    return y == 1;
}

int main () {
    int n;
    std::cin >> n;
    int ans = 0;
    for(int x = 1;x <= n ;++x ) // x: 1->n
    {
        for(int y = 1;y <= n ;++y ) // y: 1->n
        {
            int d = std::gcd(x,y);
            if( is_only_25(y / d) ) {
                printf("%d / %d \n",x,y);
                ans++;
            }
        }
    }
    std::cout << ans << "\n";
    
    return 0;
}

对于题目中的分数 $\frac{x}{y}$ （可能未化简），我们可以将分母 $y$ 分解为两部分：

y = k \times z

其中：

$z$ 是 $y$ 中只包含因子 2 和 5 的部分（即 $z = 2^a \times 5^b$ ）。
$k$ 是 $y$ 去除 2 和 5 因子后剩下的部分，此时必然满足 $\gcd(k, 10) = 1$ 。

消除因子 k

为了让 $\frac{x}{y} = \frac{x}{k \times z}$ 成为有限小数，分子 $x$ 必须能够约掉分母中的 $k$ 。这意味着 $x$ 必须是 $k$ 的倍数。即 $x = c \times k$ 。

代码2

如果我们固定 $y$ ,那么就可以求出对应的 $k$ ,y去除因子2和5,得到k,那么与之对应的x有多少个呢? 就是问 $n$ 内有多少个数字是k的倍数, $\lfloor \frac{n}{k} \rfloor$

Ans = \sum_y^n (\lfloor \frac{n}{k} \rfloor) , \text{k由y得到}

写出第二个代码,时间,接近 $O(n)$

点击

cpp

//非常暴力的算法
#include <bits/stdc++.h>
using namespace std;



//是否 y只有因子2 和 5
bool is_only_25(int y) {
    while( y % 2 == 0) y /=2;
    while( y % 5 == 0) y /=5;
    return y == 1;
}

int get_k(int y) {
    while( y % 2 == 0) y /=2;
    while( y % 5 == 0) y /=5;
    return y;
} 

int main () {
    int n;
    std::cin >> n;
    int ans = 0;
    for(int y = 1;y <= n ;++y ) // y: 1->n
    {
        int k = get_k(y);
        if( k == 0) continue;
        ans += n / k;
    }
    std::cout << ans << "\n";
    
    return 0;
}

计数转化

Open in Excalidraw

一个y对应一个k,但是k可能对应多个y. 既然枚举y不行,那我们转而去枚举 $k$

我们可以改变枚举对象：不枚举 $y$ ，而是枚举 $k$ 。对于一个固定的 $k$ （满足 $\gcd(k, 10) = 1$ ）：

$x$ 的限制：因为 $1 \le x \le n$ 且 $k|x$ ，所以合法的 $x$ 有 $\lfloor \frac{n}{k} \rfloor$ 个。
$y$ 的限制：因为 $y = k \times z \le n$ ，所以 $z \le \lfloor \frac{n}{k} \rfloor$ 。且 $z$ 必须形如 $2^a \times 5^b$ 。
- 设函数 $f(m)$ 表示 $\le m$ 的数中形如 $2^a \times 5^b$ 的数的个数。
- 那么合法的 $y$ 就对应着 $f(\lfloor \frac{n}{k} \rfloor)$ 个合法的 $z$ 。

综合上述两点，总答案为：

\text{Ans} = \sum_{k=1, \gcd(k,10)=1}^{n} \left( \lfloor \frac{n}{k} \rfloor \times f\left(\lfloor \frac{n}{k} \rfloor\right) \right)

举个例子: 当 $n=7$ ,k不同的时候:1 3 7,对应的x,y分别

k = 1
cnt x = 1 2 3 4 5 6 7
cnt y = 1 2 4 5

k = 3
cnt x = 3 6
cnt y = 3 6

k = 7
cnt x = 7
cnt y = 7

我们写出一个暴力的枚举k,然后输出方案的代码

点击

cpp

#include <bits/stdc++.h>
using namespace std;



//是否 y只有因子2 和 5
bool is_only_25(int y) {
    while( y % 2 == 0) y /=2;
    while( y % 5 == 0) y /=5;
    return y == 1;
}

int main () {
    int n;
    std::cin >> n;
    int ans = 0;
    //枚举k
    for(int k = 1; k<=n;k++) {
        if( std::gcd(k,10) == 1) {
            cout << "k = " << k << endl;
            cout << "cnt x = "  ;
            for(int t = 1 ; t *k <=n;t++)
                cout << t * k << " ";
            std::cout  << "\n";

            // 枚举y
            cout << "cnt y = ";
            for(int y = 1; y <=n;y++) {
                if( y % k != 0) continue; // y里面不含有y
                if( is_only_25(y / k) == false ) continue;
                std::cout << y << " ";
                ans +=  n /k ; // ans += cnt of x
            }
            std::cout  << "\n\n";

        }
    }
    std::cout << ans << "\n";
    
    return 0;
}

3 求f函数

如何求 $f\left(\lfloor \frac{n}{k} \rfloor = m\right)$ ? 设函数 $f(m)$ 表示 $[1, m]$ 的数中形如 $2^a \times 5^b$ 的数的个数。

只考虑 $2^a$ ,那么就有 $log_2n$ ,所有可以知道,a,b的数量不是很大

python

>>> import math
>>> math.log2(10**12)
39.86313713864835
>>> 2 ** 40 > 10 ** 12
True
>>> 2 ** 39 > 10 ** 12
False
>>> 2 ** 39 >= 10 ** 12
False
>>> math.log(10**12,5)
17.16811869688072

所有我们直接枚举就可以了

点击

cpp

#include <algorithm>
#include <bits/stdc++.h>
using namespace std;
typedef  long long ll;
ll n, ans=0;

// 存所有2^a x 5 ^b 组成的数字
std::vector<ll> a25;

// 求[1,v] 形如 2^a x 5 ^b 的数量
ll f(ll v) {
    return std::upper_bound(a25.begin(), a25.end(),v) - a25.begin();
}

ll g(ll n) {
    return n - n/2 - n/5 + n/10;
}

void init_a25() {
    std::vector<ll> a5;
    ll t = 1; a5.push_back(t);
    ll up = 1e12;
    for(int b = 1;b <= 17 ;++b ){
        t *=5;
        a5.push_back(t);
    }
    for(ll a = 0;a <= 39 ;++a ) // a: 1->39
    {
        for( auto b : a5)
        {
            ll t= (1ull << a) *  b;
            if( t >up) break;
            a25.push_back(t);
        }
    }
    std::sort(a25.begin(),a25.end());

    // for( auto a : a25) std::cout << a << " ";
    // std::cout   << "\n";
}


//是否 y只有因子2 和 5
bool is_only_25(int y) {
    while( y % 2 == 0) y /=2;
    while( y % 5 == 0) y /=5;
    return y == 1;
}

int main () {
    init_a25();
    std::cin >> n;
    //枚举k
    for(int k = 1; k<=n;k++) {
        if( std::gcd(k,10) == 1) {
            ll cnt_x = n/k;
            ll cnt_y = f(n/k);
            ans += cnt_x * cnt_y; 
        }
    }
    std::cout << ans << "\n";
    
    return 0;
}

4 算法实现与优化

直接计算上述公式仍然是 $O(n)$ 的。为了通过 $10^{12}$ 的数据，我们需要使用 整除分块 (Number Theory Blocking)。

现在上面的代码的问题: 就在于k还是需要一个一个枚举出来

我们发现一个重要的规律: 当k增长的时候, n/k 的变换是梯度下降的

import Data.List

main = do
    let n = 30
    let a = [ n `div` i | i <-[1..n]  ]
    putStrLn $ show a

bash

➜  6583 git:(main) ✗ runghc 1.hs
[30,15,10,7,6,5,4,3,3,3,2,2,2,2,2,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1]

同一块内的元素的n/k的值是一样的. 那么配合g函数(在下面👇),可以快速的求出一块内合法的数值(gcd(i,10) = 1)的数量

整除分块的代码

cpp

优化 1：整除分块

观察发现， $\lfloor \frac{n}{k} \rfloor$ 的值呈阶梯状下降。我们可以把 $\lfloor \frac{n}{k} \rfloor$ 值相同的 $k$ 归为一个区间 $[l, r]$ 统一计算。

区间右端点计算： $r = n / (n / l)$ 。
区间贡献：
$(\text{区间内与10互质的数}) \times (\lfloor \frac{n}{l} \rfloor \times f(\lfloor \frac{n}{l} \rfloor))$

优化 2：快速计算互质个数

如何快速求区间 $[l, r]$ 内与 10 互质的数的个数？利用前缀和思想：count(r) - count(l-1)。由于与 10 互质的分布具有周期性（周期为 10，互质数为 1, 3, 7, 9），我们可以 $O(1)$ 算出：

\text{count}(x) = (x / 10) \times 4 + \text{check}(x \% 10)

方法二: 容斥原理

如果要求 $i \in [1,n],\sum_1^n 1(gcd(i,10))$ , 可以使用容斥原理

$A$ 表示2的倍数
$B$ 表示5的倍数
$n - | A \cup B|$ ,如何求 $| A \cup B|$ ?
$| A \cup B| = |A| + |B| - |A \cap B|$
$|A| =\lfloor \frac{n}{2} \rfloor$
$|B| =\lfloor \frac{n}{5} \rfloor$
$|A \cap B| =\lfloor \frac{n}{10} \rfloor$

于是可以写出代码

cpp

ll g(ll n) {
    return n - n/2 - n/5 + n/10;
}

优化 3：预处理 f(v)

$f(v)$ 需要统计 $\le v$ 的 $2^a \times 5^b$ 的数量。由于 $n \le 10^{12}$ ，满足条件的数并不多（几百个）。我们可以预先生成所有 $2^a \times 5^b \le 10^{12}$ 的数，存入数组并排序。计算 $f(v)$ 时，只需使用 std::upper_bound 进行二分查找即可。

4 C++ 代码参考

我的代码

cpp

#include <algorithm>
#include <bits/stdc++.h>
using namespace std;
typedef  long long ll;
ll n, ans=0;

// 存所有2^a x 5 ^b 组成的数字
std::vector<ll> a25;

// 求[1,v] 形如 2^a x 5 ^b 的数量
ll f(ll v) {
    return std::upper_bound(a25.begin(), a25.end(),v) - a25.begin();
}

ll g(ll n) {
    return n - n/2 - n/5 + n/10;
}

void init_a25() {
    std::vector<ll> a5;
    ll t = 1; a5.push_back(t);
    ll up = 1e12;
    for(int b = 1;b <= 17 ;++b ){
        t *=5;
        a5.push_back(t);
    }
    for(ll a = 0;a <= 39 ;++a ) // a: 1->39
    {
        for( auto b : a5)
        {
            ll t= (1ull << a) *  b;
            if( t >up) break;
            a25.push_back(t);
        }
    }
    std::sort(a25.begin(),a25.end());

    // for( auto a : a25) std::cout << a << " ";
    // std::cout   << "\n";
}


//是否 y只有因子2 和 5
bool is_only_25(int y) {
    while( y % 2 == 0) y /=2;
    while( y % 5 == 0) y /=5;
    return y == 1;
}

int main () {
    init_a25();
    std::cin >> n;
    //枚举k
    // for(int k = 1; k<=n;k++) {
    //     if( std::gcd(k,10) == 1) {
    //         ll cnt_x = n/k;
    //         ll cnt_y = f(n/k);
    //         ans += cnt_x * cnt_y; 
    //     }
    // }
    // std::cout << ans << "\n";

    // n/i 是一块一块的
    // 在块内 n/i 的值是相同的
    // 我们可以利用g函数快速求出区间[l,r] 内满足gcd(k,10) =1 的k的数量
    // 所以我们按块来计算


    //整除分块
    for(ll l = 1, r ; l <= n ; l = r +1 ){
        ll v = n /l;
        if ( v == 0) r = n;
        else r = n / v;

        // 区间
        ll cnt_x = v;
        ll cnt_y = f(v);
        ll cnt_k = g(r ) - g(l-1);
        ans += (cnt_x * cnt_y * cnt_k);
    }
    std::cout << ans << "\n";

    
    return 0;
}

没有使用容斥原理的代码.

cpp

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

typedef long long ll;

ll n;
vector<ll> nums; // 存储所有 2^a * 5^b

// 预处理所有 <= 10^12 的 2^a * 5^b
void init() {
    // 2^40 > 10^12, 5^18 > 10^12，范围很小
    for (ll i = 1; i <= n; i *= 2) {
        for (ll j = i; j <= n; j *= 5) {
            nums.push_back(j);
        }
    }
    sort(nums.begin(), nums.end());
}

// 计算 1 到 x 之间与 10 互质的数的个数
ll count_coprime(ll x) {
    ll cycle = x / 10;
    ll rem = x % 10;
    // 周期内互质个数为 4 (1, 3, 7, 9)
    ll ans = cycle * 4;
    
    // 处理余数部分
    // a 数组对应 0-9 范围内与 10 互质数的累积个数
    static int a[10] = {0, 1, 1, 2, 2, 2, 2, 3, 3, 4};
    ans += a[rem];
    
    return ans;
}

// 计算 <= val 的数中，只包含因子 2 和 5 的数的个数
ll get_f(ll val) {
    // 使用 upper_bound 找到第一个 > val 的位置
    // 减去 begin() 得到的就是 <= val 的元素个数
    return upper_bound(nums.begin(), nums.end(), val) - nums.begin();
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    if (cin >> n) {
        // 特判 n 特别小的情况，防止 init 出错（虽非必要但严谨）
        if (n == 0) { cout << 0 << endl; return 0; }

        init(); // 预处理

        ll ans = 0;
        // 整除分块
        for (ll l = 1, r; l <= n; l = r + 1) {
            ll v = n / l;
            
            if (v == 0) r = n; // 防止除0错误
            else r = n / v;
            
            // 区间 [l, r] 内 k 的贡献
            ll k_count = count_coprime(r) - count_coprime(l - 1);
            
            // 累加：k的数量 * (v * f(v))
            ans += k_count * (v * get_f(v));
        }

        cout << ans << endl;
    }

    return 0;
}

这篇博文涵盖了从问题分析、数学转化到代码优化的完整过程。

在发布之前，建议你再把代码复制到你的 IDE 里，用题目给出的样例（例如 n=5 输出 21）最后验证一下，确保万无一失。祝你的博客越来越火！

目录