從前，有個古老流傳的單人遊戲是這樣的
從1~n的整數中，你可以選擇把每個數當成兩種類別的其中一種：”倍數” 和 “因數”
被歸類為”因數”的數字沒有得分，但當然的，它是有用處的，看了下一句就知道；
被歸類為”倍數”的數字(假設是M)之得分，是所有被歸類為”因數”且整除M的數字的個數。
所以舉例來說, 假設1,2,5被歸為”因數” ，3,4,6,7,8,9,10被歸為”倍數”, 總得分就是1+2+2+1+2+1+3=12。
據說有人發明了”最強之無敗策略”，可以達到最佳的總分
這種神奇的策略, 就是”倍因的道”，或簡稱”倍因道”。
總之，希望你也懂得這個道
因為給定n，要請你回答最大可能得到的得分!
TIOJ-1241: $n\le 2000$
TIOJ-1325: $t, n\le 10^5$
1241
一個困難版一個簡單版，先從1241開始。
對於每個數字，去計算它的因數中被歸類為”因數”的數量及倍數數量，如果倍數數量>前者，那這樣直接把這個數字變成”因數”答案肯定會變好。
所以就有個$\mathcal{O}(NlogN)$的做法:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
|
#include <bits/stdc++.h>
using namespace std;
#define EmiliaMyWife ios::sync_with_stdio(0); cin.tie(NULL);
#define mem(i,j) memset(i,j,sizeof (i));
using ll = int64_t;
using ull = uint64_t;
using ld = long double;
using uint = uint32_t;
const double EPS = 1e-8;
const int INF = 0x3F3F3F3F;
const ll LINF = 4611686018427387903;
const int MOD = 1e9+7;
signed main() {
EmiliaMyWife
int t;
cin >> t;
while(t--) {
int n;
cin >> n;
vector<int> ans(n + 1);
for(int i = 1; i <= n; i++) {
int res = 0;
for(int j = i * 2; j <= n; j+=i)
res++;
if(res >= ans[i]) {
ans[i] = 0;
for(int j = i * 2; j <= n; j+=i)
ans[j]++;
}
}
cout << accumulate(ans.begin(), ans.end(), 0) << '\n';
}
return 0;
}
|
1325
這題中複雜度$\mathcal{O}(TNlogN)$會太高，得往建表的方面想。
去想想n變成n+1時會發生什麼情況?
他的所有因數的倍數數量都會多一
此時就能檢查1241的條件:倍數數量>前者。
而把它變成”因數”會需要$\mathcal{O}(logN)$，最多只會有$N$個數字被變成因數。
所以複雜度會變成$\mathcal{O}(NloN+N\sqrt N)$(用平方根其實沒那麼準確，因數數量有個更緊的上界(但我不知道是多少))。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
|
#include <bits/stdc++.h>
using namespace std;
#define EmiliaMyWife ios::sync_with_stdio(0); cin.tie(NULL);
#define mem(i,j) memset(i,j,sizeof (i));
using ll = int64_t;
using ull = uint64_t;
using ld = long double;
using uint = uint32_t;
const double EPS = 1e-8;
const int INF = 0x3F3F3F3F;
const ll LINF = 4611686018427387903;
const int MOD = 1e9+7;
const int N = 1e5 + 1;
vector<int> fac[N];
int cnt[N], ans[N], res, out[N];
signed main() {
EmiliaMyWife
for(int i = 1; i < N; i++) {
for(int j = i * 2; j < N; j+=i)
fac[j].push_back(i);
}
for(int i = 1; i < N; i++) {
res += ans[i];
for(int a : fac[i]) {
if(cnt[a] < 0)
continue;
cnt[a]++;
if(cnt[a] >= ans[a]) {
res -= ans[a];
res += cnt[a];
ans[a] = 0;
cnt[a] = -1;
for(int j = a * 2; j < N; j += a) {
ans[j]++;
}
}
}
out[i] = res;
}
int t, x;
cin >> t;
while(t--)
cin >> x, cout << out[x] << '\n';
return 0;
}
|