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;
}