题解 | 循环数比较

解题思路

这是一个大数比较问题。需要比较两个重复数字构成的大数，但不能直接构造完整数字（可能溢出），需要逐位比较。

关键点：

不能直接构造完整数字
需要逐位比较两个数
处理循环节的比较
考虑数字长度不同的情况

算法步骤：

计算两个数的循环节长度
计算实际需要比较的位数
逐位比较两个数的大小

代码

cpp
java
python

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

class Solution {
public:
    string solve(long long x1, int k1, long long x2, int k2) {
        string s1 = to_string(x1);
        string s2 = to_string(x2);
        
        // 计算两个数重复后的总长度
        long long len1 = s1.length() * (long long)k1;
        long long len2 = s2.length() * (long long)k2;
        
        // 如果长度不同，可以直接比较
        if (len1 < len2) return "Less";
        if (len1 > len2) return "Greater";
        
        // 长度相同，需要逐位比较
        long long pos = 0;
        while (pos < len1) {
            char c1 = s1[pos % s1.length()];
            char c2 = s2[pos % s2.length()];
            
            if (c1 < c2) return "Less";
            if (c1 > c2) return "Greater";
            pos++;
        }
        
        return "Equal";
    }
};

int main() {
    long long x1, x2;
    int k1, k2;
    cin >> x1 >> k1 >> x2 >> k2;
    
    Solution solution;
    cout << solution.solve(x1, k1, x2, k2) << endl;
    
    return 0;
}

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

class Solution {
public:
    string solve(long long x1, int k1, long long x2, int k2) {
        string s1 = to_string(x1);
        string s2 = to_string(x2);
        
        // 计算两个数重复后的总长度
        long long len1 = s1.length() * (long long)k1;
        long long len2 = s2.length() * (long long)k2;
        
        // 如果长度不同，可以直接比较
        if (len1 < len2) return "Less";
        if (len1 > len2) return "Greater";
        
        // 长度相同，需要逐位比较
        long long pos = 0;
        while (pos < len1) {
            char c1 = s1[pos % s1.length()];
            char c2 = s2[pos % s2.length()];
            
            if (c1 < c2) return "Less";
            if (c1 > c2) return "Greater";
            pos++;
        }
        
        return "Equal";
    }
};

int main() {
    long long x1, x2;
    int k1, k2;
    cin >> x1 >> k1 >> x2 >> k2;
    
    Solution solution;
    cout << solution.solve(x1, k1, x2, k2) << endl;
    
    return 0;
}

class Solution:
    def solve(self, x1, k1, x2, k2):
        s1 = str(x1)
        s2 = str(x2)
        
        # 计算两个数重复后的总长度
        len1 = len(s1) * k1
        len2 = len(s2) * k2
        
        # 如果长度不同，可以直接比较
        if len1 < len2:
            return "Less"
        if len1 > len2:
            return "Greater"
        
        # 长度相同，需要逐位比较
        pos = 0
        while pos < len1:
            c1 = s1[pos % len(s1)]
            c2 = s2[pos % len(s2)]
            
            if c1 < c2:
                return "Less"
            if c1 > c2:
                return "Greater"
            pos += 1
        
        return "Equal"

# 读取输入
x1, k1, x2, k2 = map(int, input().split())
solution = Solution()
print(solution.solve(x1, k1, x2, k2))

算法及复杂度

算法：模拟比较
时间复杂度： $\mathcal{O(min(len1, len2))}$ ，其中 $len_1$ 和 $len_2$ 是重复后的总长度
空间复杂度： $\mathcal{O(log x1 + log x2)}$ ，用于存储数字的字符串表示