Submission #73935620

Source Code Expand

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


int main(){
  ll K,M,c,l,p = 10007,modp = 0,modM = 0,lp,lM,l9M,x;
  cin >> K >> M;
  vector<ll> X(p),Yp(32),YM(32),Y9M(32);
  X[1] = 1;
  for(ll i = 2;i < p;i++){
    X[i] = X[p % i] * (p / i);
    X[i]%=p;
    X[i] = p - X[i];
  }
  Yp[0] = 10;
  YM[0] = 10 % M;
  Y9M[0] = 10 % (9 * M);
  for(ll i = 1;i < 32;i++){
    Yp[i] = Yp[i - 1] * Yp[i - 1];
    Yp[i]%=p;
    YM[i] = YM[i - 1] * YM[i - 1];
    YM[i]%=M;
    Y9M[i] = Y9M[i - 1] * Y9M[i - 1];
    Y9M[i]%=(9 * M);
  }
  for(ll i = 0;i < K;i++){
    cin >> c >> l;
    bitset<32> L = l;
    lp = 1;
    lM = 1;
    l9M = 1;
    for(ll j = 0;j < 32;j++){
      if(L.test(j)){
        lp*=Yp[j];
      }
      lp%=p;
      if(L.test(j)){
        lM*=YM[j];
      }
      lM%=M;
      if(L.test(j)){
        l9M*=Y9M[j];
      }
      l9M%=(9 * M);
    }
    modp*=lp;
    modp%=p;
    modM*=lM;
    modM%=M;
    modp+=c * (lp - 1) * X[9];
    modp%=p;
    x = c * (l9M - 1);
    x%=(9 * M);
    x/=9;
    modM+=x;
    modM%=M;
  }
  modp-=modM;
  modp+=p;
  modp%=p;
  modp*=X[M];
  modp%=p;
  cout << modp;
}

Submission Info

Submission Time
Task E - Simple Division
User MI6174
Language C++23 (GCC 15.2.0)
Score 450
Code Size 1200 Byte
Status AC
Exec Time 48 ms
Memory 3728 KiB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 450 / 450
Status
AC × 3
AC × 43
Set Name Test Cases
Sample sample_01.txt, sample_02.txt, sample_03.txt
All hand_01.txt, hand_02.txt, hand_03.txt, hand_04.txt, hand_05.txt, sample_01.txt, sample_02.txt, sample_03.txt, test_01.txt, test_02.txt, test_03.txt, test_04.txt, test_05.txt, test_06.txt, test_07.txt, test_08.txt, test_09.txt, test_10.txt, test_11.txt, test_12.txt, test_13.txt, test_14.txt, test_15.txt, test_16.txt, test_17.txt, test_18.txt, test_19.txt, test_20.txt, test_21.txt, test_22.txt, test_23.txt, test_24.txt, test_25.txt, test_26.txt, test_27.txt, test_28.txt, test_29.txt, test_30.txt, test_31.txt, test_32.txt, test_33.txt, test_34.txt, test_35.txt
Case Name Status Exec Time Memory
hand_01.txt AC 1 ms 3688 KiB
hand_02.txt AC 1 ms 3496 KiB
hand_03.txt AC 1 ms 3496 KiB
hand_04.txt AC 1 ms 3496 KiB
hand_05.txt AC 1 ms 3680 KiB
sample_01.txt AC 1 ms 3544 KiB
sample_02.txt AC 1 ms 3688 KiB
sample_03.txt AC 1 ms 3500 KiB
test_01.txt AC 1 ms 3684 KiB
test_02.txt AC 48 ms 3544 KiB
test_03.txt AC 48 ms 3660 KiB
test_04.txt AC 47 ms 3688 KiB
test_05.txt AC 47 ms 3600 KiB
test_06.txt AC 47 ms 3500 KiB
test_07.txt AC 47 ms 3456 KiB
test_08.txt AC 47 ms 3544 KiB
test_09.txt AC 47 ms 3720 KiB
test_10.txt AC 47 ms 3660 KiB
test_11.txt AC 47 ms 3600 KiB
test_12.txt AC 47 ms 3588 KiB
test_13.txt AC 47 ms 3644 KiB
test_14.txt AC 47 ms 3588 KiB
test_15.txt AC 47 ms 3568 KiB
test_16.txt AC 47 ms 3656 KiB
test_17.txt AC 47 ms 3588 KiB
test_18.txt AC 47 ms 3600 KiB
test_19.txt AC 47 ms 3720 KiB
test_20.txt AC 47 ms 3728 KiB
test_21.txt AC 47 ms 3544 KiB
test_22.txt AC 47 ms 3688 KiB
test_23.txt AC 47 ms 3496 KiB
test_24.txt AC 47 ms 3564 KiB
test_25.txt AC 47 ms 3580 KiB
test_26.txt AC 47 ms 3544 KiB
test_27.txt AC 47 ms 3720 KiB
test_28.txt AC 47 ms 3680 KiB
test_29.txt AC 47 ms 3644 KiB
test_30.txt AC 47 ms 3544 KiB
test_31.txt AC 47 ms 3544 KiB
test_32.txt AC 47 ms 3568 KiB
test_33.txt AC 47 ms 3444 KiB
test_34.txt AC 47 ms 3588 KiB
test_35.txt AC 47 ms 3720 KiB