首页 > 代码库 > 2015年多校联合训练第一场OO’s Sequence(hdu5288)
2015年多校联合训练第一场OO’s Sequence(hdu5288)
题意:给定一个长度为n的序列,规定f(l,r)是对于l,r范围内的某个数字a[i],都不能找到一个相应的j使得a[i]%a[j]=0。那么l,r内有多少个i,f(l,r)就是几。
问全部f(l,r)的总和是多少。
公式中给出的区间,也就是全部存在的区间。
思路:直接枚举每个数字,对于这个数字,假设这个数字是合法的i,那么向左能扩展的最大长度是多少,向右能扩展的最大长度是多少。那么i为合法的情况就是左长度*右长度(包括i且i是合法的区间总数)。
统计左长度能够推断a[i]的约数是否在前面出现过…由于a[i]<=10000,能够用数组标记一下i左边的全部数字a[k],k
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
using namespace std;
const int Max = 1e5+100;
const int mod = 1e9+7;
int a[Max];
int used[Max];
long long zuo[Max];
long long you[Max];
int cal(int x)
{
int m = sqrt(x*1.0);
int maxi = max(used[1],used[x]);
for(int i = 2; i <= m; ++i)
{
if(x % i == 0)
{
maxi = max( max(maxi,used[i]), used[x/i]);
}
}
return maxi;
}
int main()
{
int n;
while(~scanf("%d",&n))
{
memset(used,0,sizeof(used));
memset(zuo,0,sizeof(zuo));
memset(you,0,sizeof(you));
for(int i = 1; i <= n; ++i )
{
scanf("%d",a+i);
zuo[i] = i - cal(a[i]);
used[a[i]] = i;
}
memset(used,0,sizeof(used));
//反过来求右边。n-i+1,自己模拟下就知道优点
for(int i = 1; i <= n; ++i)
{
you[n-i+1] = i - cal(a[n-i+1]);
used[a[n-i+1]] = i;
}
long long ans = 0;
for(int i = 1; i <= n; ++i)
{
ans +=( zuo[i]*you[i])%mod;
}
printf("%lld\n",ans%mod);
}
return 0;
}
2015年多校联合训练第一场OO’s Sequence(hdu5288)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。