Author: Nachiket Kanore
Tester: Ajinkya Kharosekar
Editorialist: Ajinkya Kharosekar
DIFFICULTY:
Medium-Hard
PREREQUISITES:
Dynamic Programming
PROBLEM:
Given an N-digit number X (without leading zeroes) Along with that a positive integer K is given.
Find the number of ways to cut X into two integers (non-empty) such that both of them are divisibly by K.
EXPLANATION:
Each valid part will be non-empty prefix and suffix of original number
So, consider all prefixes and suffixes and computer their value % k
For each i = [1,n-1] check if both values prefix[i] and suffix[i+1] are zero,
and increment count.
Solutions:
Setter's Solution
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cmath>
#include <vector>
#include <cassert>
#include <string>
#include <cstring>
#define int long long
#define pb push_back
#define ALL(x) (x).begin(),(x).end()
#define sz(x) (int)(x.size())
#define FOR(i,L,R) for(int i = (L); i <= (R); i++)
using namespace std;
template<class T> bool cmin(T& a, const T& b) { return b < a ? a = b, 1 : 0; }
template<class T> bool cmax(T& a, const T& b) { return a < b ? a = b, 1 : 0; }
const int N = 2e5 + 5, inf = 1e18;
int power(int a, int b, int mod){
int ret = 1;
a %= mod;
while(b > 0){
if(b % 2)
ret = ret * a % mod;
b /= 2;
a = a * a % mod;
}
return ret;
}
int32_t main() {
ios::sync_with_stdio(0); cin.tie(0);
int T;
cin >> T;
while (T--) {
string s;
int n, k;
cin >> n >> k;
cin >> s; s = " " + s;
int ans = 0;
vector<int> suff(n+2);
int ten = 1;
for (int i = n; i; i--) {
int dig = s[i] - '0';
suff[i] = (dig * ten + suff[i+1]) % k;
ten = (ten * 10) % k;
}
int left = 0;
FOR (i,1,n-1) {
int dig = s[i] - '0';
left = (10 * left + dig) % k;
ans += left == 0 && suff[i+1] == 0;
}
cout << ans << '\n';
}
}
Tester's Solution
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cmath>
#include <vector>
#include <cassert>
#include <string>
#include <cstring>
#define int long long
#define pb push_back
#define ALL(x) (x).begin(),(x).end()
#define sz(x) (int)(x.size())
#define FOR(i,L,R) for(int i = (L); i <= (R); i++)
using namespace std;
template<class T> bool cmin(T& a, const T& b) { return b < a ? a = b, 1 : 0; }
template<class T> bool cmax(T& a, const T& b) { return a < b ? a = b, 1 : 0; }
const int N = 2e5 + 5, inf = 1e18;
int power(int a, int b, int mod){
int ret = 1;
a %= mod;
while(b > 0){
if(b % 2)
ret = ret * a % mod;
b /= 2;
a = a * a % mod;
}
return ret;
}
int32_t main() {
ios::sync_with_stdio(0); cin.tie(0);
int T;
cin >> T;
while (T--) {
string s;
int n, k;
cin >> n >> k;
cin >> s; s = " " + s;
int ans = 0;
vector<int> suff(n+2);
int ten = 1;
for (int i = n; i; i--) {
int dig = s[i] - '0';
suff[i] = (dig * ten + suff[i+1]) % k;
ten = (ten * 10) % k;
}
int left = 0;
FOR (i,1,n-1) {
int dig = s[i] - '0';
left = (10 * left + dig) % k;
ans += left == 0 && suff[i+1] == 0;
}
cout << ans << '\n';
}
}