QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#632867#7716. Average Valuememset0AC ✓15ms9140kbC++231.5kb2024-10-12 14:06:322024-10-12 14:06:32

Judging History

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

  • [2024-10-12 14:06:32]
  • 评测
  • 测评结果:AC
  • 用时:15ms
  • 内存:9140kb
  • [2024-10-12 14:06:32]
  • 提交

answer

#include <bits/stdc++.h>
#define sz(x) ((int)(x).size())
#define all(x) begin(x), end(x)
#ifdef memset0
#define log(...) fprintf(stderr, __VA_ARGS__)
#else
#define endl '\n'
#define log(...) (void(0))
#endif
using namespace std;
using ll = long long;
using lf = long double;
using ull = unsigned long long;

const int N = 200011;
vector<int> prime;
ll Qpow(ll a, ll p, ll mod) {
  ll res = 1;
  while (p) {
    if (p & 1) res = res * a % mod;
    a = a * a % mod, p >>= 1;
  }
  return res;
}
vector<int> a[N], now, mul;
string s;
bool isprime(int x) {
  for (int i = 2; i * i <= x; i++)
    if (x % i == 0) {
      return false;
    }
  return true;
}
int main() {
#ifdef memset0
  freopen("A.in", "r", stdin);
#endif
  cin.tie(0)->sync_with_stdio(0);
  int p = 1.123e9;
  while (prime.size() < 5) {
    if (isprime(p)) {
      // cerr << p << endl;
      prime.push_back(p);
    }
    p++;
  }
  int n, l = prime.size();
  cin >> n;
  for (int k = 0; k < l; ++k) mul.emplace_back(1);
  for (int i = 1; i <= n; ++i) {
    cin >> s;
    now.clear();
    now.resize(l);
    for (int j = 0; j < s.size(); ++j)
      for (int k = 0; k < l; ++k) {
        now[k] = (now[k] * 10ll + (s[j] - '0')) % prime[k];
      }
    a[i] = now;
    for (int k = 0; k < l; ++k) mul[k] = (ll)mul[k] * a[i][k] % prime[k];
  }
  for (int i = 1; i <= n; ++i) {
    bool fail = 0;
    for (int k = 0; k < l; ++k)
      if (Qpow(a[i][k], n, prime[k]) != mul[k]) {
        fail = 1;
        break;
      }
    if (!fail) {
      cout << i << endl;
      return 0;
    }
  }
  return 0;
}

详细

Test #1:

score: 100
Accepted
time: 1ms
memory: 3584kb

input:

5
2 4 8 16 32

output:

3

result:

ok 1 number(s): "3"

Test #2:

score: 0
Accepted
time: 1ms
memory: 3660kb

input:

2
123456789012345678901234567890 123456789012345678901234567890

output:

1

result:

ok 1 number(s): "1"

Test #3:

score: 0
Accepted
time: 1ms
memory: 3652kb

input:

10
64 8 64 4096 32768 8 64 8 8 8

output:

1

result:

ok 1 number(s): "1"

Test #4:

score: 0
Accepted
time: 0ms
memory: 3596kb

input:

10
64 8 512 64 8 64 64 512 8 512

output:

1

result:

ok 1 number(s): "1"

Test #5:

score: 0
Accepted
time: 1ms
memory: 3644kb

input:

10
1000 40 40 200 40 40 8 8 40 8

output:

2

result:

ok 1 number(s): "2"

Test #6:

score: 0
Accepted
time: 0ms
memory: 3664kb

input:

10
49 1512 2286144 1764 49 12348 294 1512 12348 294

output:

4

result:

ok 1 number(s): "4"

Test #7:

score: 0
Accepted
time: 1ms
memory: 3724kb

input:

10
125 102400 12800 25 1000 1600 12800 1000000 8000 1600000

output:

9

result:

ok 1 number(s): "9"

Test #8:

score: 0
Accepted
time: 1ms
memory: 3584kb

input:

2
3 3

output:

1

result:

ok 1 number(s): "1"

Test #9:

score: 0
Accepted
time: 0ms
memory: 3648kb

input:

3
8 8 8

output:

1

result:

ok 1 number(s): "1"

Test #10:

score: 0
Accepted
time: 1ms
memory: 3724kb

input:

100
2193839575200 3781876293492931691366400000 33793357970584576000000 285803704769965200000 61509520800 25117269296464800 10193665470128758800000 247709946781718074483200 1855691370 481415333760324314396172288000000 4114068743823360000 44652923193715200 386660596224000 11899021578210392449355694489...

output:

60

result:

ok 1 number(s): "60"

Test #11:

score: 0
Accepted
time: 1ms
memory: 3656kb

input:

200
9 81 81 729 27 243 81 9 9 81 27 81 81 27 27 81 729 9 2187 243 27 243 27 27 27 81 81 243 9 9 243 9 81 81 81 243 27 243 9 9 9 243 27 243 27 6561 81 243 9 27 81 243 243 243 27 243 2187 81 27 81 9 81 243 27 27 27 27 243 27 81 9 81 243 729 9 729 81 81 27 27 81 81 9 243 2187 729 81 6561 81 9 81 6561 8...

output:

2

result:

ok 1 number(s): "2"

Test #12:

score: 0
Accepted
time: 1ms
memory: 3680kb

input:

300
194275225472 125177336 82854821923556029619961856 194275225472 120461277512968958042544258176 2412121199460352 9673914949181816 131987335565935398595712 213484188390544 4711174217696 364087463027406826976 213484188390544 4711174217696 13662988056994816 204844344798331738620545024 414159325477655...

output:

63

result:

ok 1 number(s): "63"

Test #13:

score: 0
Accepted
time: 1ms
memory: 3740kb

input:

400
21929283671882206592 17629086342434516606372576 56444365018604240608 5942867098549947776 5203911644964928 20279403032 417074727908921697898468864 16540987880081831809331551744 1307199466945456428815871170186752 92410001393311618578688 465165529952536 20132416603060217964477481792 583947363664 63...

output:

42

result:

ok 1 number(s): "42"

Test #14:

score: 0
Accepted
time: 0ms
memory: 3696kb

input:

500
21051555843900960 249850582161494430000 1816364749464001386210016931357433600000 7341768508180412121274198864656000000 61813415877324177108000 68732479319737397073067054848000 39444700594683637565548297488000 2807114314158937776000 21259947417510845911025672388000000 2642223858144886592455561473...

output:

237

result:

ok 1 number(s): "237"

Test #15:

score: 0
Accepted
time: 6ms
memory: 4136kb

input:

10000
930675254966150476697259144985 930675254966150476697259144985 930675254966150476697259144985 930675254966150476697259144985 930675254966150476697259144985 930675254966150476697259144985 930675254966150476697259144985 930675254966150476697259144985 930675254966150476697259144985 930675254966150...

output:

1

result:

ok 1 number(s): "1"

Test #16:

score: 0
Accepted
time: 2ms
memory: 3652kb

input:

20
107719672266498265320271265685604205784381792279599122302815354442418937683656313119561564257407747622723051484122122776196531317710873736680947075437249390884079983950231448281452805814938553575770634399403518420019404456036357307618141600751416322923873597821237097794397721069547931683875191740...

output:

18

result:

ok 1 number(s): "18"

Test #17:

score: 0
Accepted
time: 1ms
memory: 3644kb

input:

1000
272484 81 81 14094 81 272484 81 3840389496 47412216 126846 81 9 126846 14094 6561 10274526 126846 9 1141614 9 74247530256 126846 14094 198640836 1566 272484 1566 1566 126846 126846 9 81 9 2452356 9 81 9 729 9 2452356 9 14094 272484 1566 1566 14094 2452356 12919070264544 272484 729 272484 9 4267...

output:

4

result:

ok 1 number(s): "4"

Test #18:

score: 0
Accepted
time: 0ms
memory: 3696kb

input:

2000
313342017408 301926804480 96012723824640 101124 985352256 98535225600 3019268044800 1011240 27932737265647308767232 985352256 96012723824640 98535225600 2975042579412389068800 93554798094729216 98535225600 960127238246400 29419747828531200 28666602284120801280 9601272382464000 301926804480 2793...

output:

3

result:

ok 1 number(s): "3"

Test #19:

score: 0
Accepted
time: 2ms
memory: 3812kb

input:

3000
38024 4945782288384 177039744 177039744 38024 228144 177039744 106609084882944 13788108311527424 29506624 29674693730304 38024 228144 22897140224 177039744 228144 49817207463614028447744 228144 17768180813824 38024 137382841344 29506624 137382841344 38024 228144 29506624 1764 22897140224 294 49...

output:

3

result:

ok 1 number(s): "3"

Test #20:

score: 0
Accepted
time: 2ms
memory: 3816kb

input:

4000
23100424192 8111104 2848 8111104 8111104 2848 8111104 8111104 2848 2848 2848 8111104 8111104 65790008098816 2848 8111104 2848 2848 2848 8111104 2848 2848 23100424192 8111104 2848 2848 8111104 8111104 2848 2848 2848 23100424192 8111104 8111104 8111104 2848 2848 23100424192 23100424192 8111104 28...

output:

2

result:

ok 1 number(s): "2"

Test #21:

score: 0
Accepted
time: 2ms
memory: 3944kb

input:

5000
6 6 6 36 6 216 6 6 36 216 36 6 216 36 6 6 216 36 36 36 6 36 36 6 6 216 7776 36 216 216 6 36 36 6 6 6 6 6 6 36 36 36 46656 216 36 36 6 36 6 1296 36 216 36 6 6 1296 36 216 36 36 216 216 36 6 216 6 6 36 36 36 36 6 6 1296 216 36 36 6 6 6 6 36 6 6 216 216 216 36 216 216 216 216 36 7776 6 36 1296 36 ...

output:

4

result:

ok 1 number(s): "4"

Test #22:

score: 0
Accepted
time: 0ms
memory: 4008kb

input:

6000
5002 410164 410164 5002 61 33633448 410164 61 5002 5002 5002 5002 61 2757942736 410164 410164 5002 5002 5002 61 33633448 410164 5002 5002 410164 5002 410164 410164 33633448 61 61 33633448 33633448 5002 33633448 33633448 61 61 410164 5002 410164 61 5002 5002 5002 61 5002 5002 33633448 1854440695...

output:

2

result:

ok 1 number(s): "2"

Test #23:

score: 0
Accepted
time: 2ms
memory: 4108kb

input:

7000
16019373958966423 4913 98039 289 5434337036550550673 98039 289 98039 565390913 17 9611645521 289 565390913 3260609395271 28333271 98039 9611645521 289 4913 565390913 163397973857 1666663 98039 98039 47222014444673 565390913 565390913 289 28333271 1666663 1666663 1666663 565390913 28333271 4913 ...

output:

22

result:

ok 1 number(s): "22"

Test #24:

score: 0
Accepted
time: 3ms
memory: 4152kb

input:

8000
704731396699 704731396699 704731396699 79192201 704731396699 704731396699 79192201 79192201 8899 8899 704731396699 79192201 79192201 8899 8899 79192201 79192201 79192201 704731396699 8899 496646341493323308096601 79192201 6271404699224401 704731396699 79192201 55809230418397944499 8899 79192201...

output:

4

result:

ok 1 number(s): "4"

Test #25:

score: 0
Accepted
time: 3ms
memory: 4144kb

input:

9000
995328 46656 3779136 129140163 995328 2166612408926208 1586874322944 306110016 36864 102036672 3 19591041024 3 19591041024 2359296 46656 2008387814976 9 528958107648 2187 5159780352 241864704 1259712 387420489 12288 139968 80621568 306110016 19683 2359296 46656 419904 1259712 3779136 1719926784...

output:

3

result:

ok 1 number(s): "3"

Test #26:

score: 0
Accepted
time: 2ms
memory: 4200kb

input:

10000
9 9 6561 9 9 729 9 9 81 729 9 9 81 729 9 81 59049 9 81 81 9 9 9 81 729 9 81 9 9 729 81 729 81 81 9 81 9 81 81 9 9 81 9 59049 6561 9 9 9 9 81 9 729 81 81 81 81 9 9 81 9 6561 81 81 81 81 9 9 81 81 9 9 729 81 729 9 9 9 81 9 81 9 9 729 9 81 9 9 9 9 9 81 9 81 729 729 81 9 81 9 729 9 729 9 729 729 9...

output:

9

result:

ok 1 number(s): "9"

Test #27:

score: 0
Accepted
time: 1ms
memory: 3604kb

input:

50
694538244284066987063124452688271731257434464037430012757142459999121734133566114709337853373915642836596420514501351456469792763282885124465633202726393106153531031420575557790581730433336298800993568255901251705089373345254574564905688747816162353554473625741716162547668631111683976907714158092...

output:

2

result:

ok 1 number(s): "2"

Test #28:

score: 0
Accepted
time: 2ms
memory: 3656kb

input:

50
246833086159529361729820062016858828056021012615555351102972835701581907056439452259816752720027355527422618102678002183282150956947801309246624127117747705611717417853719731386466747578640146949970900740769806582749748621877108358809956046203646450764327565993941047756214224351790328437567765320...

output:

1

result:

ok 1 number(s): "1"

Test #29:

score: 0
Accepted
time: 2ms
memory: 3656kb

input:

50
244234490102530757483696267491341897638012331789413002250543863319875166930506860666576718107293821822992348699843884228989566132144929357197866696272103207433611347473325705425764565721763058301172601405334799003557596765972259658700373231080544851778673250884235094387274789278858527692215173886...

output:

2

result:

ok 1 number(s): "2"

Test #30:

score: 0
Accepted
time: 10ms
memory: 9064kb

input:

100000
4 2 16 8 8 2 8 2 8 2 2 2 2 8 2 2 2 2 8 8 2 8 8 8 2 8 8 2 16 8 2 2 2 2 8 2 2 2 2 2 2 8 16 8 8 8 8 8 2 2 2 8 8 8 2 16 16 2 8 2 2 2 2 2 8 2 8 8 2 2 2 2 2 8 8 8 2 2 16 2 2 8 16 2 2 2 2 2 2 8 8 16 2 8 2 2 2 8 2 16 8 8 2 8 8 2 8 8 8 8 2 8 2 2 2 2 16 8 8 16 2 8 2 8 2 8 2 8 2 8 2 2 16 2 2 2 8 2 8 2 2...

output:

1

result:

ok 1 number(s): "1"

Test #31:

score: 0
Accepted
time: 14ms
memory: 9120kb

input:

100000
32 32 64 32 32 8 128 8 32 8 32 8 8 32 64 8 8 8 8 8 32 4 8 64 4 8 64 64 64 32 32 32 8 8 256 8 4 128 8 4 4 8 64 64 8 8 32 8 4 8 64 8 64 64 64 8 4 8 64 4 32 8 64 8 32 32 8 8 8 32 128 32 64 128 8 8 8 32 128 32 4 8 64 64 8 8 32 8 8 8 8 32 32 4 8 64 8 8 8 128 32 32 8 32 8 32 8 8 8 32 8 128 8 8 2 12...

output:

100000

result:

ok 1 number(s): "100000"

Test #32:

score: 0
Accepted
time: 15ms
memory: 9116kb

input:

100000
3 27 3 27 27 3 3 81 3 3 27 81 3 3 27 27 3 81 3 81 81 3 81 27 3 27 243 243 81 27 3 3 27 3 3 81 27 27 27 3 81 3 81 27 3 27 27 3 3 243 243 3 3 3 3 27 3 27 3 3 3 27 81 3 3 3 81 81 81 81 27 27 27 27 27 27 81 3 3 3 27 243 27 81 3 81 81 3 3 27 81 3 3 81 27 27 27 27 3 3 3 243 3 3 27 81 27 3 3 3 81 3 ...

output:

50001

result:

ok 1 number(s): "50001"

Test #33:

score: 0
Accepted
time: 14ms
memory: 9140kb

input:

100000
13 13 2197 13 2197 13 2197 13 2197 28561 2197 28561 13 13 2197 13 13 2197 13 13 13 28561 13 2197 13 2197 2197 13 2197 2197 2197 2197 13 13 2197 2197 13 13 13 2197 13 13 28561 13 13 13 28561 28561 13 2197 2197 2197 13 13 2197 2197 28561 13 13 13 13 2197 2197 2197 13 13 2197 2197 2197 13 13 13 ...

output:

75001

result:

ok 1 number(s): "75001"

Test #34:

score: 0
Accepted
time: 4ms
memory: 3720kb

input:

10
899609752893731039710367640386056236307981789880401416394779011187503455205417806965867810062753228850135746726495831131774856999191026524752187614686603346987528769544727399737510750630891937211741483586946708174675821529874504642595198718609120213020809842224760202148910186210449332483470084640...

output:

6

result:

ok 1 number(s): "6"

Test #35:

score: 0
Accepted
time: 5ms
memory: 3760kb

input:

10
431072033542237365099490480780172157668249363207935246616598091052076488702623394861158652442454471948047350883808718849331182865771004353995803425263710662565336848303026680165701753038619987219810032678039076088777759212528898312106704232274028047099229726376510350277516267853320350958698689377...

output:

3

result:

ok 1 number(s): "3"

Test #36:

score: 0
Accepted
time: 5ms
memory: 3732kb

input:

10
358696585919493472175316420341354937539525193180581605894864412160889566578520967549350653965081340182889631335036004112361327247201753694264744328527252115201974077140784799891446134189128887983480346359018228373501466926667960602655427864404834805855391138498322815187905683074462607773552064160...

output:

2

result:

ok 1 number(s): "2"

Test #37:

score: 0
Accepted
time: 5ms
memory: 3696kb

input:

10
571190362363956061795962061271526672346830862104324230318282879581216560896491095662307468214065537825252115436608138726744626270373466708224602135099350050505537227387775105590822872665900511044817264393530029997492961551647802451933685732728036107761617806522538774343749311005660247332239856566...

output:

1

result:

ok 1 number(s): "1"

Test #38:

score: 0
Accepted
time: 5ms
memory: 3792kb

input:

10
316126944390696070274928436473412800647704740661900327830075618358067428939152308953688455864925246243880886109815566325338697442444327074088347272315529100882385730692648899720735315667550883182848343426086478953414250557834198406999301630123619222296981503336922374284904029047504016168980347627...

output:

4

result:

ok 1 number(s): "4"

Test #39:

score: 0
Accepted
time: 8ms
memory: 9124kb

input:

100000
153 153 153 153 153 153 153 153 153 153 153 153 153 153 153 153 153 153 153 153 153 153 153 153 153 153 153 153 153 153 153 153 153 153 153 153 153 153 153 153 153 153 153 153 153 153 153 153 153 153 153 153 153 153 153 153 153 153 153 153 153 153 153 153 153 153 153 153 153 153 153 153 153 1...

output:

1

result:

ok 1 number(s): "1"

Test #40:

score: 0
Accepted
time: 13ms
memory: 9124kb

input:

100000
999 999 999 999 999 999 999 999 999 999 999 999 999 999 999 999 999 999 999 999 999 999 999 999 999 999 999 999 999 999 999 999 999 999 999 999 999 999 999 999 999 999 999 999 999 999 999 999 999 999 999 999 999 999 999 999 999 999 999 999 999 999 999 999 999 999 999 999 999 999 999 999 999 9...

output:

1

result:

ok 1 number(s): "1"