Problem Description
WLD likes playing with a sequence a[1..N]. One day he is playing with a sequence of N integers. For every index i, WLD wants to find the smallest index F(i) ( if exists ), that i<F(i)≤n, and aF(i) mod ai = 0. If there is no such an index F(i), we set F(i) as 0.
Input
There are Multiple Cases.(At MOST 10)
For each case:
The first line contains one integers N(1≤N≤10000).
The second line contains N integers a1,a2,...,aN(1≤ai≤10000),denoting the sequence WLD plays with. You can assume that all ai is distinct.
Output
For each case:
Print one integer.It denotes the sum of all F(i) for all 1≤i<n
Sample Input
4 1 3 2 4
Sample Output
6
Hint
F(1)=2 F(2)=0 F(3)=4 F(4)=0---------------------------------------------------------------------华丽的分割线-------------------------------------------------------------------
维护一个vis数组 vis[i]记录i上一次出现的位置，从右往左遍历给出的数字，每个数字num都从vis[num * 2]从左往右暴力vis数组
时间复杂度为O(n/1+n/2+…+n/n)=O(nlogn)
1 #include<cstdio> 2 #include<algorithm> 3 #include<cstring> 4 using namespace std; 5 const int maxn = 10050; 6 int num[maxn]; int vis[maxn]; 7 int main() 8 { 9 int n; 10 while(scanf("%d", &n) == 1) { 11 int maxnum = 0; 12 for(int i = 0 ; i < n ; i++) scanf("%d", &num[i]), maxnum = max(maxnum, num[i]); 13 memset(vis, 0, sizeof(vis)); 14 int ans = 0; 15 for(int i = n - 1 ; i >= 0 ;i--) { 16 vis[num[i]] = i + 1; int id = 0x3f3f3f3f; 17 for(int j = num[i] * 2 ; j <= maxnum ; j += num[i]) { 18 if(vis[j]) 19 id = min(id, vis[j]); 20 } 21 if(id != 0x3f3f3f3f) ans += id; 22 ///printf("%d\n", ans); 23 } 24 printf("%d\n", ans); 25 } 26 return 0; 27 }