首页 > 代码库 > Codesforces 485D Maximum Value
Codesforces 485D Maximum Value
D. Maximum Value
You are given a sequence a consisting of n integers. Find the maximum possible value of 
(integer remainder of ai divided byaj), where 1 ≤ i, j ≤ n and ai ≥ aj.
Input
The first line contains integer n — the length of the sequence (1 ≤ n ≤ 2·105).
The second line contains n space-separated integers ai (1 ≤ ai ≤ 106).
Output
Print the answer to the problem.
Sample test(s)
input
3
3 4 5
output
2
给出 n 个数 a[0] ~ a[n-1] ，要你找出 a[i] % a[j] 最大.
处理一个数组x[i]表示 1~i 离i最近的数是什么。就可以过了。
#include <bits/stdc++.h>using namespace std;typedef long long LL;const int mod = (1e9+7);const int N = 2000010;bool num[N];int x[N] , a;int main(){ int n ; cin >> n ; for( int i = 0 ; i < n ; ++i ) { cin >> a; num[a] = 1 ; } for( int i = 0 ; i <= 2e6 ; ++i ){ if( num[i] )x[i] = i ; else x[i] = x[i-1] ; } int res = 0 ; for( int i = 1 ; i <= 1e6 ; ++i ) if( num[i] ){ for( int j = 2 * i ; j <= 2e6 ; j += i ) { res = max( res , ( x[j-1] ) % i ); } } cout << res << endl;}
Codesforces 485D Maximum Value
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。