TIOJ 1325 倍因道 - EXTREME

    poao899    1948K    326MS    G++     0.89K     2010-03-29 00:10:54                                    .



我說code風格好醜= =


然後用1241來Debug...不行   思路不夠清楚






O(n ln n)+ T*O(1)


//**************************

#include<stdio.h>
#include<algorithm>
#define MAX 100000
struct stuff{
    int ori, cmp;
    bool operator<(const stuff &b)const{
        return cmp<b.cmp;
    }
}s[100010];
int sieve[100010], dp[100010], get[100010], t, n;
int main(){
   
    for(int i=1; i<=MAX; i++)
        for(int j=i+i; j<=MAX; j+=i)
            sieve[j]++;

    for(int i=1; i<=MAX; i++){
        s[i-1].ori= i;
        s[i-1].cmp= (sieve[i]+1)* i;
    }
    std::sort(s, s+MAX);
    for(int i=1,j=0; i<=MAX; i++){
        dp[i]= dp[i-1];
        while(j<MAX&& s[j].cmp<=i){
            dp[i]-= sieve[s[j].ori];
            for(int z=s[j].ori*2; z<=MAX; z+=s[j].ori){
                if(z<i)dp[i]++;
                get[z]++;
            }
            j++;
        }
        dp[i]+= get[i];
    }
    scanf("%d", &t);
    while(t--){
        scanf("%d", &n);
        printf("%d\n", dp[n]);
    }
}