题目解析

问题描述

给定一个以1、3、7或9结尾的数字字符串，我们需要找到一个数字，使得该数字的立方恰好以给定的数字字符串结尾。找到的数字的位数不应超过给定字符串的位数。

输入输出

• 输入：首先输入测试用例的数量，然后每个测试用例给出一个以1、3、7或9结尾的数字字符串。
• 输出：对于每个测试用例，输出一个数字，其立方以给定的字符串结尾，且该数字的位数不超过输入字符串的位数。

示例

输入：

4
123
1234567
435621
9876543213

输出：

947
2835223
786941
2916344917

解题思路

关键观察

1. 数字结尾特性：由于输入字符串以1、3、7或9结尾，我们可以利用这些数字的立方结尾特性来快速确定答案的最低有效位。
2. 模运算应用：为了确保数字的立方以给定字符串结尾，可以利用模运算逐步构建数字，从最低位到最高位逐位确定。

算法设计

1. 初始化：根据输入字符串的最后一位数字，确定答案的最后一位数字。
   • 如果最后一位是1，则答案的最后一位是1。
   • 如果最后一位是3，则答案的最后一位是7。
   • 如果最后一位是7，则答案的最后一位是3。
   • 如果最后一位是9，则答案的最后一位是9。
2. 逐位构建：从倒数第二位开始，逐步向高位扩展，每次确定一位数字。
   • 对于当前确定的位数，计算当前部分数字的立方模10^k（k为当前位数），并与输入字符串的对应部分比较。
   • 通过逐步调整当前数字，直到其立方模10^k与输入字符串的对应部分匹配。
3. 结果输出：最终构建的数字即为所求，其立方以输入字符串结尾。

复杂度分析

• 时间复杂度：对于每个测试用例，处理时间为O(n)，其中n为字符串的长度。由于字符串长度最多为10，整体效率较高。
• 空间复杂度：仅需常数空间存储中间变量，空间复杂度为O(1)。

解决代码

#include <iostream>
#include <string>
using namespace std;

long long multiplyAndMod(long long a, long long b, long long mod) {
    long long result = 0;
    while (b > 0) {
        if (b % 2 == 1) {
            result = (result + a) % mod;
        }
        a = (a * 2) % mod;
        b /= 2;
    }
    return result;
}

long long computeCubeMod(long long x, long long mod) {
    long long square = multiplyAndMod(x, x, mod);
    return multiplyAndMod(square, x, mod);
}

int main() {
    int testCases;
    cin >> testCases;
    while (testCases--) {
        string inputStr;
        cin >> inputStr;
        int length = inputStr.length();
        long long target = stoll(inputStr);
        long long result = 0;
        long long power = 1;

        // Determine the last digit of the result
        char lastChar = inputStr[length - 1];
        if (lastChar == '1') result = 1;
        else if (lastChar == '3') result = 7;
        else if (lastChar == '7') result = 3;
        else if (lastChar == '9') result = 9;

        power = 10;

        for (int i = length - 2; i >= 0; --i) {
            long long currentDigit = inputStr[i] - '0';
            long long currentTarget = currentDigit * power + target % power;
            long long step = power / 10;
            while (computeCubeMod(result, power * 10) % (power * 10) != currentTarget) {
                result += step;
            }
            power *= 10;
        }
        cout << result << endl;
    }
    return 0;
}

代码解释

1. 输入处理：读取测试用例数量和每个测试用例的字符串。
2. 初始化结果：根据输入字符串的最后一位数字，初始化结果的最后一位。
3. 逐位构建数字：从倒数第二位开始，逐步向高位扩展。每次调整当前数字，直到其立方模10^k与输入字符串的对应部分匹配。
4. 输出结果：最终的数字即为所求，其立方以输入字符串结尾。

标程

#include <iostream>  
#include <string>


using namespace std;


long long mulAndMod(long long a, long long b, long long mod) {  //  a * b % mod
	long long c;
	const int base = 2;  //  base可以取任意大于1的整数
	for (c = 0; b != 0; b /= base) {
		c += (b % base) * a;
		c %= mod;
		a = (a * base) % mod;
	}
	return c;
}


long long cube(long long x, long long mod){  //  x^3 % y = (x^2 % y) * x % y
	return mulAndMod(mulAndMod(x, x, mod), x, mod);
}


int main() { 
	int t;
	long long result;  //  答案，从右向左一位位增加
	long long remain;  //  从右向左一位位地和待比较的数比较
	long long power;
	long long step;
	string str;  //  待比较的数
	int length;  //  待比较数的长度
	
	
	cin >> t;
	while (t--){
		cin >> str;
		length = str.length();
		remain = str[length - 1] - '0';  //  初始化，取待比较的数最低位
		
		
		if (remain == 1) result = 1;  //  待比较的数最低位若为1，则答案最低位为1
		else if (remain == 3) result = 7;  //  待比较的数最低位若为3，则答案最低位为7
		else if (remain == 7) result = 3;  //  待比较的数最低位若为7，则答案最低位为3
		else if (remain == 9) result = 9;  //  待比较的数最低位若为9，则答案最低位为9
		
		
		power = 10;
		
		
		for (int i = length - 2; i >= 0; --i){  //  从待比较数的倒数第二位开始
			remain += (str[i] - '0') * power;  //  更新remain值
			
			
			step = power;
			power *= 10;  //  若remain有两位，则模数为100；若remain有三位，则模数为1000……
			
			//  (result^3 % power)与remain比较，直到相等。此时result低位中对应remain的那几位已经确定
			while (cube(result, power) != remain){
				//  若remain有两位，则result每次加10即可；若remain有三位，则result每次加100即可……
				result += step;
			}
		}
		cout << result << '\n';
	}
	
	
	return 0;
}