C. C. Blog

Security Research, Algorithm and Data Structure

51Nod 1421 最大MOD值

Problem

有一个a数组,里面有n个整数。现在要从中找到两个数字(可以是同一个) ai,aj ,使得 ai mod aj 最大并且 ai ≥ aj。

Solution

遍历模数,枚举倍数,对于每一个倍数,找到比倍数小的最大值。这个最大值之前预处理出来,注意细节。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
#include<stdio.h>
#include<iostream>
#include<cstring>
#include<algorithm>
#include<map>
#define io_opt ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
using namespace std;
#define db double
#define ll long long
inline int rd(){
int x=0;
char ch=0;
while(ch<'0'||ch>'9') {ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x;
}
int n,a[200020],mx,ans;
int f[1000020];
int main(){
//io_opt;
n=rd();
for(int i=1;i<=n;i++){
a[i]=rd();
mx=max(mx,a[i]);
}
sort(a+1,a+1+n);
n=unique(a+1,a+1+n)-(a+1);
a[n+1]=1000000;
for(int i=1;i<=n;i++){
for(int j=a[i]+1;j<=a[i+1];j++){
f[j]=a[i];
}
}
for(int i=1;i<=n;i++){
for(int k=2;;k++){
int sum=k*a[i]>1000000?mx:f[k*a[i]];
ans=max(ans,sum%a[i]);
if(k*a[i]>1000000) break;
}
}
printf("%d\n",ans);
return 0;
}
  • 本文作者: CCWUCMCTS
  • 本文链接: https://ccwucmcts.github.io/posts/57254/
  • 版权声明: 本博客所有文章除特别声明外,均采用 BY-NC-SA 许可协议。转载请注明出处!