OJ: luogu
题目 ID: P3131
标签: 数论前缀和
日期: 2025-12-31 15:35
题目解析
核心思想:
暴力代码
cpp
#include <iostream>
using namespace std;
const int maxn = 1e5+5;
int n;
int s[maxn];
int ans;
int main(int argc, char const *argv[])
{
cin >> n;
for(int i =1;i<=n;i++) {
cin >> s[i];
s[i] += s[i-1];// si = si-1 + a[i]
}
for(int i =1;i<=n;i++) {
for(int j = i;j<=n;j++)
{
// cout << i<< " " << j << endl;
int t= s[j] - s[i-1];
if( t % 7 == 0) {
int len = j-i+1;
if( ans < len)
ans = len;
}
}
}
cout << ans;
return 0;
}
代码
cpp
/**
* Author by Rainboy blog: https://rainboylv.com github : https://github.com/rainboylvx
* rbook: -> https://rbook.roj.ac.cn https://rbook2.roj.ac.cn
* date: 2025-12-31 16:46:37
*/
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const ll maxn = 2e6+5;
ll n,m;
ll a[maxn];
ll pre[maxn];
ll first[10];
ll last[10];
signed main () {
ios::sync_with_stdio(false); cin.tie(0);
std::cin >> n;
for(ll i = 1;i <= n ;++i ) // i: 1->n
{
std::cin >> a[i];
pre[i] = pre[i-1] + a[i];
}
// 7 | a -b
// a \equiv b \pmod 7
for(ll i = 0;i <= 6 ;++i ) // i: 0->6
{
last[i] = first[i] = -1; // 表示不存在
}
// 特殊判断
first[0] = last[0] = 0;
for(ll i = 1;i <= n ;++i ) // i: 1->n
{
ll mod = pre[i] % 7;
if( first[mod] == -1) first[mod] = i;
last[mod] = i;
}
ll ans = -1;
for(ll i = 0;i <= 6 ;++i ) // i: 0->6
{
ll len = last[i] - first[i];
if( ans < len) ans = len;
}
std::cout << ans << "\n";
return 0;
}