Code bài SUMCAL trên NTU bị sai

#1

Các nghiên cứu toán học :https://oeis.org/A057723

Đề bài

Và đây là code của em bị sai ?!

#include <bits/stdc++.h>
#define fi(i, a, b) for(int i=a; i<=b; i++)
#define fid(i, a, b) for(int i=a; i>=b; i--)
#define ll long long
#define mod 1000000007
#define maxn 100005

using namespace std;

ll binpow(ll u, int v){
    if (v == 1) return u;
    int x = binpow(u, v/2);
    if (v%2 == 1) return (u * (x*x%mod)) % mod;
    return (x*x) % mod;
}

ll a[maxn];

int main(){
    int t;
    cin >> t;
    while (t--){
        ll n, res = 1;
        cin >> n;
        fi(i, 1, n){
            cin >> a[i];
            res = (res * a[i]) % mod;
        }
        fi(i, 1, n){
            int x;
            cin >> x;
            res = (res * (binpow(a[i], x) - 1) / (a[i]-1)) % mod;
        }
        cout << res << '\n';
    }
}

Vì mod là nguyên tố khá to nên chắc chắn gcd(a_i-1, mod)
nên a_i^x-1 chia hết cho a_i-1 thì (a_i^x-1) (\bmod 10^9+7) vẫn chia hết cho a_i-1

Và các số là ước của N' = A_1 ^ {B_1-1} * A_2^{B_2-1} *....A_M^{B_M-1} rồi nhân với A_1 A_2....A_M là tất cả các số thỏa mãn đề rồi

#4

Lý do rất đơn giản, do tràn số.

int x = binpow(u, v/2);

x < 1e9+7, x kiểu int, vậy x*x có kiểu gì, và xui nhất x = 1e9 + 6 thì x*x có giá trị bao nhiêu?

Mà lạ ta, hàm binpow trả về long long mà bạn khai báo biến int để lưu giá trị làm gì?

4 Likes
#5

Không được đâu bạn ạ. Cho dù đổi hết int sang long long.
Mà contest gì mà test 2 đã vừa to vừa nhiều rồi, làm mình chả biết sai ở đâu.

image
image946×525 25.5 KB

#6

a_i^x - 1 đã lấy dư với 1e9 + 7 rồi thì làm sao chia hết cho a_i-1 được nữa? Muốn chia, bạn tìm hiểu inverse modulo.

5 Likes
#7

Sử dụng nghịch đảo xong em thấy vẫn sai test 2 :frowning:. Em cũng đã test thử 1 vài kết quả lớn rồi :frowning:
Lí do em thêm biến long long x thì đơn giản thôi, em không muốn gọi đệ quy 2 lần, nên chắc tiết kiệm được 1 xíu time

Code 
#include <bits/stdc++.h>
#define fi(i, a, b) for(int i=a; i<=b; i++)
#define ll long long
#define maxn 100005

using namespace std;

const int mod = 1e9+7;

ll binpow(ll u, ll v){
    if (v == 1) return u;
    ll x = binpow(u, v/2);
    if (v%2) return (u * (x*x%mod)) % mod;
    return (x*x) % mod;
}

ll a[maxn];

int main(){
    int t;
    cin >> t;
    while (t--){
        ll n, x, res = 1;
        cin >> n;
        fi(i, 1, n) {cin >> a[i]; res = (res * a[i]) % mod;}
        fi(i, 1, n){
            cin >> x;
            res = (res * (binpow(a[i], x) - 1)) % mod;
            res = (res * binpow(a[i] - 1, mod-2)) % mod;
        }
        cout << res << '\n';
    }
}
1 Like
#8

đáp án chắc là S = \prod\limits_{i=1}^{M}{\left(\dfrac{A_i^{B_i + 1} - 1}{A_i - 1} - 1\right)}

ví dụ đã tìm được đáp án S_{k-1} với A_1^{B_1} tới A_{k-1}^{B_{k-1}} rồi, bây giờ thêm 1 ước nguyên tố nữa thành A_1^{B_1} tới A_k^{B_k}, thì S_k = (A_k + A_k^2 + ... + A_k^{B_k})S_{k-1}. Mà ta có q^{n+1} - 1 = (q - 1)(1 + q + q^2 + ... + q^n) nên suy ra A_k + A_k^2 + ... + A_k^{B_k} = \dfrac{A_k^{B_k + 1} - 1}{A_k- 1} - 1. Từ đó có công thức trên.

tính x = A_i^{B_i + 1} \mod p thì “dễ” rồi. Tính y = x - 1 \mod p cũng dễ: tính (x + p - 1) % p là được. Có chia là hơi khó, nhưng vì p là số nguyên tố rồi nên thật ra cũng dễ: tính z = \dfrac{y}{A_i - 1} \mod p bằng tính z = y (A_i - 1)^{p - 2} \mod p là được :V

def factor(a, b, P):
    x = pow(a, b + 1, P)
    y = (x + P - 1) % P
    z = y * pow(a - 1, P - 2, P) % P
    return (z + P - 1) % P

def answer(A, B, P):
    res = 1
    for i in range(len(A)):
        res = res * factor(A[i], B[i], P) % P
    return res
    
if __name__ == '__main__':
    P = 1_000_000_007
    print(answer([2, 3, 103], [3, 2, 1], P)) # đáp án 17304 cho 7416

có vẻ đúng đây :triumph:

3 Likes
#9

S = \prod\limits_{i=1}^{M}{\left(\dfrac{A_i^{B_i + 1} - 1}{A_i - 1} - 1\right)} = \prod\limits_{i=1}^{M}{\left(\dfrac{A_i^{B_i + 1} - A_i}{A_i - 1} \right)}= \prod\limits_{i=1}^{M}{\left(\dfrac{A_i}{A_i - 1}(A_i^{B_i} - 1) \right)}= \prod\limits_{i=1}^{M}{A_i} \prod\limits_{i=1}^{M}{\dfrac{A_i^{B_i} - 1}{A_i - 1} }
Em cũng đâu khác gì :slight_smile:

P/s: KLQ nhưng nhìn cái \prod\limits_{i=1}^{M}{\dfrac{A_i}{A_i - 1}} như phi hàm bị đảo ý :smile:

2 Likes
#10

A_i kia sao rút ra ngoài rồi thành 2 cái product gì là sao :V :V

chỉ có hằng số hoặc biến ko lệ thuộc vào i mới được phép rút ra chứ đâu có rút biến lệ thuộc vào i như A_i ra được :V

edit à có thể lấy ra được ở đây là product phép nhân :V :V

2 Likes
#11

em sợ cái A_i^{B_i} khi lấy mod nó <A_i nên phải để thế

#12

.
vậy tính thẳng \dfrac{A_i^{B_i + 1} - 1}{A_i - 1} luôn :thinking:

1 Like
#13

ủa mà code này còn bị sai à :V Em tính theo công thức kia cũng đúng mà :V

có thể là do input/output chậm? Em thử thêm

ios_base::sync_with_stdio(false);
cin.tie(0);

trước khi xài cin cout xem :V

5 Likes
#14

Haizz, vẫn không được, em nghĩ là test sai thật rồi. Để em thử nốt xử lí số lớn xem sao :frowning:

#15

à có thể do - 1 sai đó

res = (res * (binpow(a[i], x) - 1)) % mod;

ví dụ binpow(a[i], x) mà = 0 thì trừ 1 nó ra số âm nên tính sai :V Phải tính x-1 theo kiểu (x + mod - 1) % mod

3 Likes
#16

Em biết sai ở đâu rồi ạ, các số nguyên tố chưa chắc phân biệt :frowning:
Thảo nào em thấy đâu cần đk SNT < 1e6 làm gì :frowning:

3 Likes
83% thành viên diễn đàn không hỏi bài tập, còn bạn thì sao?