[TIOJ 1241] 倍因道 Factor and Points

這題我是去查解才會的，但證不出來為什麼這樣是對的........
如果有一天證出來了會在這補上(?

作法：

把題目要分的組叫作A和B好了，這樣比較不會搞混。從 1 開始，每次看他放A比較好還是放B比較好，而判斷的條件是如果放 A 就假設他的倍數通通都被放到 B 了，這樣是他的最高得分，而如果放B那得分就是他的因數在A裡的個數，這可以用類似篩法的方法在每次把數字加進A的時候維護好。如果放A有機會比較好就放A，否則放B。

====================================

3/5 更新證明：

當有一個數 a 被丟進A的時候，代表我們認為之後的最好情形( 也就是 a 的倍數都在 B )的 a 造成的貢獻會比把 a 移到 B 還多 ( 這時的貢獻是 a 的因數個數 )，但如果在之後的決定裡面 2a , 3a , ... , ka 們也跳槽進入A了，那 a 的貢獻就有可能變得太少以至於把 a 丟進B會更好，以下要證明這件事情不可能。

(以下的中括號為高斯符號，d(x) 代表 x 的因數個數)
用反證法，因為 ka 被放入A，由我們的決策方法可以得到 [ n/ ( k a ) ] >= d( k a )，又因為 a 的貢獻為 [ n / a ] - k ，所以此時有 [ n / a ] - k < d( a )，而考慮 [ n/ ( k a ) ] 和 [ n / a ] - k 兩個數，前者是 1~n 裡面 ka 的倍數個數，另一個是 1~n 裡面大於 ka 的 a 的倍數個數，顯然一個數整除 ka 就會整除 a ，所以後者會大於等於前者，也就是 [ n / a ] - k >= [ n/ ( k a ) ]，所以 d( a ) > [ n / a ] - k >= [ n/ ( k a ) ] >= d( k a ) ，得到了 a 的因數個數比 ka 的因數個數多，矛盾。

code :

#include<bits/stdc++.h>
using namespace std;
 
int num[3000] ;
 
main()
{
    int T ; scanf("%d",&T) ;
    while(T--)
    {
        int n ; scanf("%d",&n) ;
        memset(num,0,sizeof(num)) ;
        int ans=0 ;
        for(int i=1;i<=n;i++)
        {
            if(num[i] < n/i-1)
                for(int j=2*i;j<=n;j+=i) num[j]++ ;
            else ans+=num[i] ;
        }
        printf("%d\n",ans) ;
    }
}