HDU 4961 Boring Sum 构造题

用一个数组c， c[i]表示i这个数出现的最近数字是几。

那么当加入一个6，则 c[1] = c[2] = c[3] = c[6] = 6;

==最近怎么都要开挂啊。。

#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long ll;
const int N = 100005;
inline void rd(int &n){    
	n = 0;
    char c = getchar();    
    while(c < '0' || c > '9') c = getchar();    
    while(c >= '0' && c <= '9') n *= 10, n += (c - '0'),c = getchar();     
}    
inline void pt(int n){    
    if(n < 0)  
        putchar('-'), n = -n;    
    int len = 0,data[20];    
    while(n)    
        data[len++] = n%10, n /= 10;     
    if(!len) data[len++] = 0;    
    while(len--) putchar(data[len]+48);    
}  
int a[N], b[N], c[N], p[N];
int main() {
    int n;
    while(~scanf("%d", &n) && n) {
        
        memset(p, 0, sizeof p);
        for(int i = 1; i <= n; i ++)rd(a[i]);
        for(int i = 1; i <= n; i ++) {
            if(p[a[i]]) b[i] = p[a[i]];
            else b[i] = a[i];
            
            p[1] = p[a[i]] = a[i];
            for(int j = 2; j * j <= a[i]; j ++ ) {
                if(a[i] % j == 0) {
                    p[j] = a[i];
                    p[a[i]/j] = a[i];
                }
            }
        }
        
        memset(p, 0, sizeof p);
        for(int i = n; i > 0; i --) {
            if(p[a[i]]) c[i] = p[a[i]];
            else c[i] = a[i];
            
            p[1] = p[a[i]] = a[i];
            for(int j = 2; j * j <= a[i]; j ++ ) {
                if(a[i] % j == 0) {
                    p[j] = a[i];
                    p[a[i]/j] = a[i];
                }
            }
        }
        ll ans = 0;
        for(int i = 1; i <= n; i ++) {
            ans += (ll)b[i] * c[i];
        }
        cout << ans << endl;
    }
    return 0;
}

HDU 4961 Boring Sum 构造题,布布扣,bubuko.com

HDU 4961 Boring Sum 构造题

原文：http://blog.csdn.net/qq574857122/article/details/38686969