文章

27

粉丝

0

获赞

130

访问

8.3k

头像
P2015 涂颜色 答疑提问:
jsd VIP
P2015 上海交通大学机试题
发布于2025年3月14日 14:07
阅读数 308

这个样例通过了42%, 求助哪里出了问题

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

int main() {
    string n, m;
    cin>>n>>m;
    long long temp, ans;
    ans = 1;
    temp = 2;
    for(int i = n.size() - 1; i >= 0; i--) {
        if(n[i] != '0') {
            int cnt =  n[i] - '0';
            long long t = 1; 
            for(int j = 0; j < cnt; j++) {
                t = t * temp % 1000000007;
            }    
            ans = ans * t % 1000000007;
        }
    &nb...

登录查看完整内容


登录后发布评论

1 条评论
admin SVIP
2025年3月14日 16:25

计算逻辑错误
代码的核心逻辑是将大整数 n 按位拆分,然后通过循环计算 2^n。但是,在计算过程中,内层循环和外层循环的逻辑存在问题。具体来说,内层循环 for(int j = 0; j < cnt; j++) 是计算 temp^cnt,这里的 temp 是之前的幂次结果。而外层循环每次将 temp 进行 10 次平方操作 for(int j = 0; j < 10; j++),这不符合快速幂算法的正确逻辑。
 

#include <iostream>
#include <string>
#define MOD 1000000007

using namespace std;

// 快速幂函数
long long fastPow(long long base, long long exponent) {
    long long result = 1;
    while (exponent > 0) {
        if (exponent % 2 == 1) {
            result = result * base % MOD;
        }
        base = base * base % MOD;
        exponent /= 2;
    }
    return result;
}

int main() {
    string n;
    cin >> n;

    long long ans = 1;
    long long base = 2;

    // 从高位到低位处理大整数 n
    for (int i = 0; i < n.size(); i++) {
        ans = fastPow(ans, 10);
        int digit = n[i] - '0';
        ans = ans * fastPow(base, digit) % MOD;
    }

    cout << ans << endl;
    return 0;
}

 

赞(0)