QOJ.ac

QOJ

ID	题目	提交者	结果	用时	内存	语言	文件大小	提交时间	测评时间
#589952	#1425. Div	Afterlife^#	TL	1662ms	3700kb	C++20	2.7kb	2024-09-25 20:48:11	2024-09-25 20:48:12

Judging History

你现在查看的是最新测评结果

[2024-09-25 20:48:12]
评测

测评结果：TL
用时：1662ms
内存：3700kb

查看

[2024-09-25 20:48:11]
提交

answer

#include <bits/stdc++.h>
using namespace std;
int n , m;
const int D = 30;
typedef long double db;
map<int,int> mp;
const int px[] = {1000000007 , 1000000009 , 998244353} ;
const int pl = 3;

int qpow(int a,int b,int mod) {
    int ans = 1;
    while(b) {
        if(b & 1) ans = 1LL * ans * a %mod;
        a = 1LL * a * a % mod ;b >>= 1;
    }
    return ans;
}

bool check(int x) {
    vector<int> v , v2;
    for(int i = 0;i < pl;i++) {
        int p = px[i] , ans = 0;
        for(auto [a,c] : mp) {
            ans = (ans + 1LL * ((c + p) % p) * qpow(x , a , p) % p) % p;

        }
        ans = 1LL * ans * qpow((qpow(x , m , p) - 1 + p) % p , p - 2 , p)  % p;

        v.push_back(ans) ;
        v2.push_back((p - ans) % p) ;
        // printf("x = %d , ans = %d , p = %d\n",x,ans,p) ;
    }
    bool ff = 1;
    for(int i = 1;i < pl;i++) {
        if(v[i] != v[i - 1]) ff = 0;
    }
    if(ff) return 1;
    ff=1;
    for(int i = 1;i < pl;i++) {
        if(v2[i] !=  v2[i - 1]) ff = 0;
    }
    return ff;
}
typedef pair<int,int> pii;
const db eps = 1e-6;
mt19937 rnd( time(0)) ;
void solv() {
    cin >> n >> m;
    mp.clear() ;
    int ans = 0;
    int sol = 0;
    for(int i = 1;i <= n;i++) {
        int c , a;
        cin >> c >> a;
        // c = rnd()%2 ? 1 : -1 ;
        // a = rnd()%m;
        sol = (sol + c) % m;
        mp[a % m] += c; 
        mp[(a + 1) % m] -= c;
    }
    if(sol == 0) ans++ ;

    bool ff = 1;
    for(auto [x,y] : mp) {
        ff &= (y == 0) ;
    }
    if(ff) {
        cout << -1 << '\n' ; return ;
    }
    if(m <= 20) {
        for(int i = 2;i <= n*2 + 5;i++) ans += check(i) ;
        cout << ans << '\n' ; return ;
    }
    auto it = mp.lower_bound(m - D) ;
    vector<pii> coe;
    while(it != mp.end()) {
        coe.push_back(*it);
        it++ ;
    }
    // for(auto [a,c] : coe) cout << c <<' ' << a << '\n' ;
    for(int i = 2;i <= n * 2 + 5;i++) {
        if(i <= 20) ans += check(i) ;
        else {
            db sol = 0;
            int lst = D + 1;
            for(auto [a,c] : coe) {
                a = m - a;
                while(lst > a + 1) {
                    sol = sol / i ; lst-- ;
                }
                sol = (sol + c) / i; lst-- ;
            }
            while(lst > 1) {
                sol /= i ; lst-- ;
            }
            int dd = (int)(sol + 0.5) ;
            if(fabs(sol - dd) < eps && fabs(sol) > eps) {
                // cout << i <<' ' << sol << endl;
                ans += check(i);
            }
        }
    }
    cout << ans << '\n';
    return ;
}
int main() {
    ios::sync_with_stdio(false) ; cin.tie(0) ;
    int t;cin >> t;
    while(t--) solv() ;
    
}

源文件, 语言: C++20

详细

Test #1:

score: 100

Accepted

time: 0ms

memory: 3692kb

input:

output:

1
-1
2

result:

ok 3 number(s): "1 -1 2"

Test #2:

score: 0

Accepted

time: 0ms

memory: 3644kb

input:

1
1 1
1 0

output:

-1

result:

ok 1 number(s): "-1"

Test #3:

score: 0

Accepted

time: 0ms

memory: 3696kb

input:

4
1 1000000000
1 0
1 1
1 1000000000
1 1000000000
-1 0
1 1
-1 1000000000

output:

0
-1
0
-1

result:

ok 4 number(s): "0 -1 0 -1"

Test #4:

score: 0

Accepted

time: 740ms

memory: 3700kb

input:

output:

-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
...

result:

ok 100000 numbers

Test #5:

score: 0

Accepted

time: 346ms

memory: 3648kb

input:

output:

-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
...

result:

ok 50000 numbers

Test #6:

score: 0

Accepted

time: 1662ms

memory: 3700kb

input:

100000
1 170035890
1 835589389
1 433027164
1 407537923
1 293860673
-1 788447900
1 838946623
1 450237482
1 629410117
1 476559978
1 171248763
1 671271287
1 468119514
1 346821429
1 112217885
-1 249186444
1 760504335
1 622839250
1 206432863
1 481956490
1 344167459
-1 251322298
1 603763257
-1 255443178
1...

output:

result:

ok 100000 numbers

Test #7:

score: -100

Time Limit Exceeded

input:

18185
6 462481634
-1 877399979
-1 444077256
1 863609811
1 737864979
-1 36285324
1 213052314
10 318224330
-1 392130699
-1 865648776
1 786577813
-1 47209814
-1 582014903
-1 552524598
1 931469640
-1 520667488
1 246701061
-1 583303124
6 255562733
-1 824922940
1 140907808
-1 659810174
1 755380312
1 78398...

output: