[abc] E - Rem of Sum is Num 公式推导+mp处理

前言

传送门 :

推完公式 ！

思路

区间和 用 前缀和处理

因此题目就变成求 有多少对 ( S [ i ] − S [ j ] ) % k = i − j (S[i] - S[j])\%k = i-j (S[i]−S[j])%k=i−j

即 : S [ i ] − S [ j ] = k ∗ a + i − j S[i] - S[j] = k*a + i-j S[i]−S[j]=k∗a+i−j ( a a a一个常数) S [ i ] − i − ( s [ j ] − j ) = k ∗ a S[i] - i - (s[j]-j) = k*a S[i]−i−(s[j]−j)=k∗a ( s [ i ] − i ) % k = ( s [ j ] − j ) % k (s[i]-i)\%k = (s[j]-j)\%k (s[i]−i)%k=(s[j]−j)%k

因此我们可以先预处理除一个 长度为 m i n ( k − 1 , n ) min(k-1,n) min(k−1,n)的区间 然后我们直接计算即可

CODE

#include 
using namespace std;
#define int  long long
#define ll long long
#define endl '\n'
const int N  = 2e5+10;
int x,f[N];
map mp;

void solve()
{
    int n,k;cin>>n>>k;

    for(int i=1;i>f[i];
        f[i] += f[i-1];
    }

    for(int i=1;i