I have a question！

杨瑞 · 2025 年4 月 13 日 01:17

屏幕截图 2025-04-13 091334
题目见上
谁能帮我挑挑错！！

#include <iostream>
#include <vector>
#include <cmath>

using namespace std;
#define int __int128
inline void read(int &n){
    int x=0,f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){
        if(ch=='-') f=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9'){
        x=(x<<1)+(x<<3)+(ch^48);
        ch=getchar();
    }
    n=x*f;
}
inline void print(int n){
    if(n<0){
        putchar('-');
        n*=-1;
    }
    if(n>9) print(n/10);
    putchar(n % 10 + '0');
}
#undef int
const int MAXN = 1e5 + 5;
const int LOG = 30; // 足够覆盖1e5的范围

long long st[MAXN][LOG];
long long mod;   
    int Q;

void buildST(int n) {
    for (int i = 1; i <= n; i++) {
        st[i][0] = i % mod;
    }
    
    for (int j = 1; j < LOG; j++) {
        for (int i = 1; i + (1 << j) - 1 <= n; i++) {
            st[i][j] = (st[i][j-1] * st[i + (1 << (j-1))][j-1]) % mod;
        }
    }
}

long long query(int l, int r) {
    if (l > r) return 1;
    long long res = 1;
    for (int j = LOG-1; j >= 0; j--) {
        if (l + (1 << j) - 1 <= r) {
            res = (res * st[l][j]) % mod;
            l += (1 << j);
        }
    }
    return res;
}

int main() {
    
    cin >> Q >> mod;
    
    // 最大可能的n是1e5
    buildST(1e5);
    
    while (Q--) {
        int n, r;
        cin >> n >> r;
        
        if (r >= n) {
            cout << '0' << '\n';
        //    continue;
        }
		 else{
			 long long ans = query(r+1, n);
	        cout << ans << '\n';	
		 }
        
    }
    
    return 0;
}

王建力 · 2025 年4 月 13 日 03:06

_int128 有使用，导致过程中超出范围，输出了负数

杨瑞 · 2025 年4 月 13 日 03:16

老师，改成了这样WA：

#include <iostream>
#include <vector>
#include <cmath>

using namespace std;

inline void print(int n){
    if(n<0){
        putchar('-');
        n*=-1;
    }
    if(n>9) print(n/10);
    putchar(n % 10 + '0');
}
const int MAXN = 1e5 + 10;
const int LOG = 30; // 足够覆盖1e5的范围

__int128 st[MAXN][LOG];
int mod;   
    int Q;

void buildST(int n) {
    for (int i = 1; i <= n; i++) {
        st[i][0] = i % mod;
    }
    
    for (int j = 1; j < LOG; j++) {
        for (int i = 1; i + (1 << j) - 1 <= n; i++) {
            st[i][j] = (st[i][j-1] * st[i + (1 << (j-1))][j-1]) % mod;
        }
    }
}

int query(int l, int r) {
    if (l > r) return 1;
    int res = 1;
    for (int j = LOG-1; j >= 0; j--) {
        if (l + (1 << j) - 1 <= r) {
            res = (res * st[l][j]) % mod;
            l += (1 << j);
        }
    }
    return res;
}

int main() {
    
    cin >> Q >> mod;
    
    // 最大可能的n是1e5
    buildST(1e5);
    
    while (Q--) {
        int n, r;
        cin >> n >> r;
        
        if (r >= n) {
            cout << '0' << '\n';
        //    continue;
        }
		 else{
			 int ans = query(r+1, n);
	        print(ans);	
	        cout<<endl;
		 }
        
    }
    
    return 0;
}

杨瑞 · 2025 年4 月 13 日 03:19

#include <iostream>
#include <vector>
#include <cmath>

using namespace std;
#define int __int128
inline void print(int n){
    if(n<0){
        putchar('-');
        n*=-1;
    }
    if(n>9) print(n/10);
    putchar(n % 10 + '0');
}
const int MAXN = 1e5 + 10;
const int LOG = 30; // 足够覆盖1e5的范围

__int128 st[MAXN][LOG];
long long mod, Q;

void buildST(int n) {
    for (int i = 1; i <= n; i++) {
        st[i][0] = i % mod;
    }
    
    for (int j = 1; j < LOG; j++) {
        for (int i = 1; i + (1 << j) - 1 <= n; i++) {
            st[i][j] = (st[i][j-1] * st[i + (1 << (j-1))][j-1]) % mod;
        }
    }
}

int query(int l, int r) {
    if (l > r) return 1;
    int res = 1;
    for (int j = LOG-1; j >= 0; j--) {
        if (l + (1 << j) - 1 <= r) {
            res = (res * st[l][j]) % mod;
            l += (1 << j);
        }
    }
    return res;
}

signed main() {
    
    cin >> Q >> mod;
    
    // 最大可能的n是1e5
    buildST(1e5);
    
    while (Q--) {
        long long n, r;
        cin >> n >> r;
        
        if (r >= n) {
            cout << '0' << '\n';
        //    continue;
        }
		 else{
			 int ans = query(r+1, n);
	        print(ans);	
	        cout<<endl;
		 }
        
    }
    
    return 0;
}

这样对吗

杨瑞 · 2025 年4 月 13 日 03:33

老师，WA95：

#include <iostream>
#include <vector>
#include <cmath>

using namespace std;
#define int __int128

inline void print(int n) {
    if (n < 0) {
        putchar('-');
        n *= -1;
    }
    if (n > 9) print(n / 10);
    putchar(n % 10 + '0');
}

const int MAXN = 1e5 + 10;
const int LOG = 17; 

int st[MAXN][LOG];
long long mod;

void buildST(int n) {
    for (int i = 1; i <= n; i++) {
        st[i][0] = i % mod;
    }
    
    for (int j = 1; j < LOG; j++) {
        for (int i = 1; i + (1 << j) - 1 <= n; i++) {
            st[i][j] = (st[i][j - 1] * st[i + (1 << (j - 1))][j - 1]) % mod;
        }
    }
}

int query(int l, int r) {
    if (l > r) return 1;
    int res = 1;
    for (int j = LOG - 1; j >= 0; j--) {
        if (l + (1 << j) - 1 <= r) {
            res = (res * st[l][j]) % mod;
            l += (1 << j);
        }
    }
    return res;
}

signed main() {
    long long Q;
    cin >> Q >> mod;
    
    buildST(1e5);
    
    while (Q--) {
        long long n, r;
        cin >> n >> r;
        
        if (r >= n) {
            cout << "1\n";
        } else {
            int ans = query(r + 1, n);
            print(ans);
            cout << '\n';
        }
    }
    
    return 0;
}

杨瑞 · 2025 年4 月 13 日 03:39

老师，还有哪里要改？：

#include <iostream>
#include <vector>
#include <cmath>

using namespace std;
#define int __int128
inline void print(int n){
    if(n<0){
        putchar('-');
        n*=-1;
    }
    if(n>9) print(n/10);
    putchar(n % 10 + '0');
}
const int MAXN = 1e5 + 10;
const int LOG = 30; // 足够覆盖1e5的范围

__int128 st[MAXN][LOG];
long long mod, Q;

void buildST(int n) {
    for (int i = 1; i <= n; i++) {
        st[i][0] = i % mod;
    }
    
    for (int j = 1; j < LOG; j++) {
        for (int i = 1; i + (1 << j) - 1 <= n; i++) {
            st[i][j] = (st[i][j-1] * st[i + (1 << (j-1))][j-1]) % mod;
        }
    }
}

int query(int l, int r) {
    int res = 1%mod;
    for (int j = LOG-1; j >= 0; j--) {
        if (l + (1 << j) - 1 <= r) {
            res = (res * st[l][j]) % mod;
            l += (1 << j);
        }
    }
    return res;
}

signed main() {
    
    cin >> Q >> mod;
    
    // 最大可能的n是1e5
    buildST(1e5);
    
    while (Q--) {
        long long n, r;
        cin >> n >> r;
        
        if (r >= n) {
            cout << '0' << '\n';
        //    continue;
        }
		 else{
			 int ans = query(r+1, n);
	        print(ans);	
	        cout<<endl;
		 }
        
    }
    
    return 0;
}