# CFR 776 C. Molly's Chemicals ( Math )

Problem - 776C - Codeforces

The first line of input contains two integers, n and k, the number of chemicals and the number, such that the total affection value is a non-negative power of this number k. (1 ≤ n ≤ 1e5, 1 ≤ |k| ≤ 10).
Next line contains n integers a1, a2, ..., an ( - 1e9 ≤ ai ≤ 1e9) — affection values of chemicals.

O( N lg( MAXA * N ) )

```#include <bits/stdc++.h>
using namespace std;

const int MAXN = int( 1e5 );

int N, K;
int A[ MAXN ];
long long pA[ MAXN + 1 ];

signed main() {
ios::sync_with_stdio( 0 );
cin >> N >> K;
for( int i = 0; i < N; ++i ) {
cin >> A[ i ];
pA[ i + 1 ] = pA[ i ] + A[ i ];
}
long long ans = 0;
for( long long k = 1; ; ) {
static set< long long > vis;
if( vis.count( k ) ) break;
vis.emplace( k );
map< long long, int > cnt;
for( int i = 1; i <= N; ++i ) {
++cnt[ pA[ i - 1 ] ];
if( cnt.count( pA[ i ] - k ) ) {
ans += cnt[ pA[ i ] - k ];
}
}
if( fabs( 1.0 * k * K ) > 1e14 ) break;
k *= K;
}
cout << ans << endl;
return 0;
}
```