Multiple of 2019

​​D - Multiple of 2019​​

先把串反轉，用​

​sum[i]​

​​儲存​

​1~i​

​所表示的數。

數字是很大的，很顯然我們不能夠直接儲存數字，于是會想到兩種辦法，一個是另外想想有沒有别的思路可以避免這個問題，還有另一種方法就是将得出的數字對2019進行取模，這對是否能夠被2019整除是沒有任何影響的。

如果不能想到别的辦法，那就想想還能不能夠優化已有的思路。

// Created by CAD on 2020/4/26.
#include <bits/stdc++.h>

#define ll long long
using namespace std;

const int maxn=2e5+5;
ll sum[maxn];
const int mod=2019;
ll qpow(ll x,ll n){
    ll ans=1;
    while(n>0){
        if(n&1) ans=ans*x%mod;
        n>>=1,x=x*x%mod;
    }
    return ans;
}
map<ll,ll> cnt;
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    string s;cin>>s;
    int n=s.length();
    for(int i=0;i<n;++i)
        sum[i+1]=s[i]-'0';
    reverse(sum+1,sum+1+n);
    ll ans=0;
    cnt[0]++;
    for(int i=1;i<=n;++i){
        sum[i]=(sum[i-1]+sum[i]*qpow(10,i-1)%mod)%mod;
        ans+=cnt[sum[i]];
        cnt[sum[i]]++;
    }
    cout<<ans<<"\n";
    return 0;
}