ABC158 E - Divisible Substring
問題
N桁の数字があり、それらの連続する部分文字列のなかで素数Pで割り切れるものの個数を求めよ
方針
格桁ごとのmod Pを持ちたくなる
持つ
単純な例で言えば、P = 5の場合は一桁目が0か5ならそれ以上の桁がなんであれPで割り切れる
2もそうである
これはなぜかというと、一桁目以上は10 ^ iがかかっていて、確実に割り切れるから考慮する必要がないということである
つまりこれらP = 2, 5の場合は単純にO(N)で求めることができる
それら以外の場合、少し考える必要がある
桁ごとに見るべきなのは変わらない
結局区間のMODなので、Zero Sum Rangesでよい
345677889の4567は、(45677889 - 7889)/10^4だが、分子が0にならない限りこの値のMODもゼロにならないのである
別の見方をすると、P = 2,5の場合は、0除算になってしまうので、別で処理するべきだということにもなる
code:cpp
using namespace std;
#define rep(i,N) for(int i=0;i<int(N);++i) #define rep1(i,N) for(int i=1;i<int(N);++i) #define all(a) (a).begin(),(a).end() #define dump(x) cerr<<#x<<": "<<x<<endl; typedef long long ll;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
const int INF = (ll)1e9;
const ll INFLL = (ll)1e18+1;
const double PI = acos(-1.0);
/*
const int dx8 = {1, 0, -1, 0, 1, -1, -1, 1}; const int dy8 = {0, 1, 0, -1, 1, 1, -1, -1}; const string dir = "DRUL";
*/
int N,P;
struct mint {
long long x; // typedef long long long long;
mint(long long _x=0):x((_x%P+P)%P){}
mint operator-() const { return mint(-x);}
mint& operator+=(const mint a) {
if ((x += a.x) >= P) x -= P;
return *this;
}
mint& operator-=(const mint a) {
if ((x += P-a.x) >= P) x -= P;
return *this;
}
mint& operator*=(const mint a) {
(x *= a.x) %= P;
return *this;
}
mint operator+(const mint a) const {
mint res(*this);
return res+=a;
}
mint operator-(const mint a) const {
mint res(*this);
return res-=a;
}
mint operator*(const mint a) const {
mint res(*this);
return res*=a;
}
mint modpow(long long t) const {
if (!t) return 1;
mint a = modpow(t>>1);
a *= a;
if (t&1) a *= *this;
return a;
}
// for prime P
mint inv() const {
return modpow(P-2);
}
mint& operator/=(const mint a) {
return (*this) *= a.inv();
}
mint operator/(const mint a) const {
mint res(*this);
return res/=a;
}
};
int main() {
cin.tie(0);
ios::sync_with_stdio(false);
cout << fixed << setprecision(20);
cin>>N>>P;
string S;
cin>>S;
if(10 % P == 0){//2 or 5
ll ans = 0;
rep(r,N){
if ((Sr - '0') % P == 0){ ans += r+1;
}
}
cout<<ans<<endl;
return 0;
}
vector<mint> cumsum(N+1, 0);
rep(i,N){
cumsumi+1 = cumsumi + mint(10).modpow(N-1-i) * (Si - '0'); }
vector<int> cnt(P,0);
ll ans = 0;
rep(i,N+1){
}
for(int i = 0; i < P; ++i){
ans += cnti * (cnti - 1) / 2; }
cout<<ans<<endl;
}