fork download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. #define ll long long
  4.  
  5. using namespace std;
  6.  
  7. void solve() {
  8.     int p; cin >> p;
  9.     string s; cin >> s;
  10.     int n = s.size(), ans = 0;
  11.     s = " " + s;
  12.  
  13.     vector <int> dp_cur(p + 5, 0);
  14.     for (int i = 1; i <= n; ++i) {
  15.         int num = s[i] - '0';
  16.         vector <int> dp_new(p + 5, 0);
  17.         for (int j = 0; j < p; ++j) if (dp_cur[j])
  18.             dp_new[(j * 10 + num) % p] = 
  19.             max(dp_new[(j * 10 + num) % p], dp_cur[j] + 1);
  20.         dp_new[num % p] = max(dp_new[num % p], 1);
  21.  
  22.         ans = max(ans, dp_new[0]);
  23.         swap(dp_cur, dp_new);
  24.     }
  25.  
  26.     cout << (!ans ? -1 : ans);
  27. }
  28.  
  29. int main() {
  30.     ios_base::sync_with_stdio(0);
  31.     cin.tie(0); cout.tie(0);
  32.  
  33.     if (fopen("digits.inp", "r")) {
  34.         freopen("digits.inp", "r", stdin);
  35.         freopen("digits.out", "w", stdout);
  36.     }
  37.  
  38.     solve();
  39.  
  40.     return 0;
  41. }
Success #stdin #stdout 0.01s 5292KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
-1
https://ideone.com/zdL0QI
language:
C++14 (clang 8.0)
created:
5 hours ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!