Mutiple
Accepts: 476
Submissions: 1025
Time Limit: 4000/2000 MS (Java/Others)
Memory Limit: 65536/65536 K (Java/Others)
问题描述
wld有一个序列a[1..n], 对于每个1≤i<n, 他希望你求出一个最小的j（以后用记号F(i)表示），满足i<j≤n, 使aj为ai的倍数（即aj mod ai＝0），若不存在这样的j，那么此时令F(i) = 0
保证1≤n≤10000,1≤ai≤10000 对于任意 1≤i≤n, 且对于任意1≤i,j≤n(i!=j)，满足ai != aj
输入描述
多组数据(最多10组)
对于每组数据：
第一行：一个数n表示数的个数
接下来一行：n个数，依次为a1,a2,…,an
输出描述
对于每组数据：
输出F(i)之和(对于1≤i<n)
输入样例
4
1 3 2 4
输出样例
6
Hint
F(1)=2
F(2)=0
F(3)=4
F(4)=0
#include<stdio.h>
#include<string.h>
#include<vector>
const int M = 1e4 + ;
std::vector <int> g[M] ;
int f[M] ;
int a[M] ;
int n ; void init ()
{
for (int i = ; i <= ; i ++) {
for (int j = i ; j <= ; j += i ) {
g[j].push_back (i) ;
}
}
} int main ()
{
// freopen ("a.txt" , "r" , stdin ) ;
init () ;
while (~ scanf ("%d" , &n)) {
for (int i = ; i <= n ; i ++) scanf ("%d" , &a[i]) ;
memset (f , , sizeof(f)) ;
int sum = ;
for (int i = n; i > ; i --) {
sum += f[a[i]] ;
// printf ("a[%d]=%d , f = %d\n" , i , a[i] , f[a[i]]) ;
for (int j = ; j < g[a[i]].size () ; j ++) {
f[ g[a[i]][j] ]= i ;
}
}
printf ("%d\n" , sum ) ;
}
return ;
}
杰神教的打法，其实是令求1 ， 2 ， ……n的每个数的因子复杂度降到O（n/1 + n/2 + n/3 ……n/n） = O（nlogn） ，所以平均下来就是O（logn）了。