[蓝桥杯]矩阵翻硬币

矩阵翻硬币

题目描述

小明先把硬币摆成了一个 nn 行 mm 列的矩阵。

随后，小明对每一个硬币分别进行一次 QQ 操作。

对第 x 行第 y 列的硬币进行 QQ 操作的定义：将所有第 i×xi×x 行，第 j×yj×y 列的硬币进行翻转。

其中 ii 和 jj 为任意使操作可行的正整数，行号和列号都是从 1 开始。

当小明对所有硬币都进行了一次 QQ 操作后，他发现了一个奇迹：所有硬币均为正面朝上。

小明想知道最开始有多少枚硬币是反面朝上的。于是，他向他的好朋友小 M 寻求帮助。

聪明的小 M 告诉小明，只需要对所有硬币再进行一次 QQ 操作，即可恢复到最开始的状态。然而小明很懒，不愿意照做。于是小明希望你给出他更好的方法。帮他计算出答案。

输入描述

输入数据包含一行，两个正整数 n,mn,m，含义见题目描述。

其中，n、m≤101000n、m≤101000。

输出描述

输出一个正整数，表示最开始有多少枚硬币是反面朝上的。

输入输出样例

示例

输入

2 3
```txt
>输出
```txt
1

运行限制

• 最大运行时间：2s
• 最大运行内存: 256M

总通过次数: 444  |  总提交次数: 573  |  通过率: 77.5%

难度: 困难   标签: 2014, 省赛, 二分

矩阵翻硬币算法思路

这个问题需要高效计算大规模矩阵中初始反面硬币的数量，关键在于数学优化和大数处理。核心思路如下：

1. ​​翻转规律分析​​：

   • 每个位置(x,y)的翻转次数 = (x的约数个数) × (y的约数个数)
   • 初始为反面的硬币必须被翻转奇数次 → 要求约数个数均为奇数
   • ​​只有完全平方数有奇数个约数​​（例如4的约数：1,2,4）

2. ​​数学转换​​：

   • 反面硬币数量 = ⌊√n⌋ × ⌊√m⌋
   • 例如n=3, m=3时：√3≈1.7 → ⌊1.7⌋=1 → 结果=1

3. ​​大数处理​​：

   • n,m可达10¹⁰⁰⁰ → 需要实现字符串形式的大数开平方和乘法
   • 开平方算法采用​​竖式开方法​​（按位确定），乘法采用​​竖式乘法​​

算法步骤演示（竖式开方示例）

以√1024为例：

分组：10'24
 余数   | 当前根 | 操作
--------|--------|----------------
 10     |   0    | 0²=0<10 → 选3
 10-9=1 |   3    | 拼接24 → 124
 124    |   3    | (3 * 20+2)*2=124
 0      |   32   | 结束 → √1024=32

完整C++代码实现

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

// 去除前导零
string removeLeadingZeros(string s) {
    int start = 0;
    while (start < s.size() && s[start] == '0') start++;
    return (start == s.size()) ? "0" : s.substr(start);
}

// 比较两个大数 (1:a>b, 0:a==b, -1:a<b)
int compare(string a, string b) {
    a = removeLeadingZeros(a);
    b = removeLeadingZeros(b);
    if (a.length() != b.length()) 
        return a.length() > b.length() ? 1 : -1;
    if (a == b) return 0;
    return a > b ? 1 : -1;
}

// 大数减法 (a>=b)
string subtract(string a, string b) {
    int i = a.length() - 1, j = b.length() - 1;
    int borrow = 0;
    string res = "";
    
    while (i >= 0 || j >= 0) {
        int digit_a = (i >= 0) ? a[i--] - '0' : 0;
        int digit_b = (j >= 0) ? b[j--] - '0' : 0;
        int diff = digit_a - digit_b - borrow;
        
        if (diff < 0) {
            diff += 10;
            borrow = 1;
        } else {
            borrow = 0;
        }
        res.push_back(diff + '0');
    }
    reverse(res.begin(), res.end());
    return removeLeadingZeros(res);
}

// 大数乘以一位数
string multiplyChar(string s, int d) {
    if (d == 0 || s == "0") return "0";
    string res = "";
    int carry = 0;
    
    for (int i = s.size() - 1; i >= 0; i--) {
        int product = (s[i] - '0') * d + carry;
        carry = product / 10;
        res.push_back((product % 10) + '0');
    }
    
    if (carry) res.push_back(carry + '0');
    reverse(res.begin(), res.end());
    return res;
}

// 大数加法
string add(string a, string b) {
    int i = a.size() - 1, j = b.size() - 1;
    int carry = 0;
    string res = "";
    
    while (i >= 0 || j >= 0 || carry) {
        int sum = carry;
        if (i >= 0) sum += a[i--] - '0';
        if (j >= 0) sum += b[j--] - '0';
        carry = sum / 10;
        res.push_back((sum % 10) + '0');
    }
    
    reverse(res.begin(), res.end());
    return res;
}

// 大数开平方
string sqrtBig(string s) {
    int len = s.length();
    int groupNum = (len + 1) / 2;
    vector<string> groups;
    
    // 按两位分组
    if (len % 2 == 1) {
        groups.push_back(s.substr(0, 1));
        for (int i = 1; i < len; i += 2) {
            groups.push_back(s.substr(i, 2));
        }
    } else {
        for (int i = 0; i < len; i += 2) {
            groups.push_back(s.substr(i, 2));
        }
    }
    
    string remainder = "0";
    string sqrtRes = "";
    
    for (int i = 0; i < groupNum; ++i) {
        string current = remainder == "0" ? groups[i] : remainder + groups[i];
        current = removeLeadingZeros(current);
        
        for (int d = 9; d >= 0; --d) {
            string base = sqrtRes == "" ? "0" : multiplyChar(sqrtRes, 2) + "0";
            string basePlusD = add(base, to_string(d));
            string temp = multiplyChar(basePlusD, d);
            
            if (compare(current, temp) >= 0) {
                remainder = subtract(current, temp);
                sqrtRes += ('0' + d);
                break;
            }
        }
    }
    return sqrtRes;
}

// 大数乘法
string multiply(string a, string b) {
    if (a == "0" || b == "0") return "0";
    int m = a.size(), n = b.size();
    vector<int> resArr(m + n, 0);
    
    for (int i = m - 1; i >= 0; --i) {
        for (int j = n - 1; j >= 0; --j) {
            int product = (a[i] - '0') * (b[j] - '0');
            int pos1 = i + j, pos2 = i + j + 1;
            int sum = product + resArr[pos2];
            
            resArr[pos2] = sum % 10;
            resArr[pos1] += sum / 10;
        }
    }
    
    string res;
    for (int num : resArr) {
        if (!res.empty() || num != 0) {
            res.push_back(num + '0');
        }
    }
    return res.empty() ? "0" : res;
}

int main() {
    string n, m;
    cin >> n >> m;
    
    string sqrt_n = sqrtBig(n);
    string sqrt_m = sqrtBig(m);
    
    string result = multiply(sqrt_n, sqrt_m);
    cout << removeLeadingZeros(result) << endl;
    
    return 0;
}

代码解析

1. ​​关键函数​​：

   • sqrtBig()：实现大数开平方，按位确定平方根
   • multiply()：大数乘法，优化时间复杂度为O(n²)
   • subtract()/compare()：辅助大数运算

2. ​​开平方流程​​：

   • ​​分组处理​​：每2位一组（奇数位首位单独分组）
   • ​​余数计算​​：current = 余数 + 当前组
   • ​​试商逻辑​​：从9→0尝试满足(2×当前根×10 + d)×d ≤ current
   • ​​更新状态​​：余数减去乘积，追加d到平方根

3. ​​乘法优化​​：

   • 使用进位数组存储中间结果
   • 双重循环计算每位乘积
   • 时间复杂度O(len₁×len₂)

实例验证

测试点与边界

1. ​​特殊输入​​：

   • n="0"/m="0" → 输出0
   • n="1" m="1" → 输出1
   • n="9...9"(1000位) → 验证√(10¹⁰⁰⁰)=10⁵⁰⁰

2. ​​性能测试​​：

   • 10³位数字：开平方约500次迭代
   • 10⁶位乘法：约10¹²操作（需优化）

3. ​​正确性测试​​：

   Input: "16" "16" → Output: "16" (4×4)
   Input: "1000000" "1000000" → Output: "1000000" (1000×1000)

优化建议

1. ​​算法级优化​​：

   • ​​牛顿迭代法​​：开平方收敛更快（二次收敛）
   • ​​FFT乘法​​：大数乘法优化到O(n log n)
   • ​​预处理​​：存储平方根结果复用

2. ​​代码级优化​​：

   • ​​内存复用​​：避免频繁字符串创建
   • ​​并行计算​​：乘法内层循环并行化
   • ​​Karatsuba​​：分治乘法优化性能

3. ​​异常处理​​：

   • 添加非法字符检测
   • 前导零预处理
   • 内存溢出保护