T1 div
给定\(m\)个不同的正整数\(a_1\)，\(a_2\)，\(\cdots\)请对\(1\)到\(n\)每一个\(k\)计算，在区间\([1,n]\)里有多少正整数是\([a_1,a_m]\)中恰好\(k\)个数的约数。
暴力拆解就可以了。
int main()
{
poread(n);
poread(m);
for(register int i = 1, x; i <= m; ++i)
{
poread(x);
for(register int j = 1, lim = min(n, (int)sqrt(x)); j <= lim; ++j)
{
if(x % j == 0)
{
v[++tot] = j;
if(j * j != x && x / j <= n)
v[++tot] = x / j;
}
}
}
sort(v + 1, v + 1 + tot);
register int sum = 0;
for(register int i = 1, cnt = 1; i <= tot && v[i] <= n; ++i)
{
v[i] == v[i - 1] ? ++cnt : (++ans[cnt], cnt = 1, ++sum);
}
ans[0] = n - sum;
for(register int i = 0; i <= m; ++i)
printf("%d\n", ans[i]);
return 0;
}T2 market
在比特镇一共有\(n\)家商店，编号依次为\(1\)到\(n\)。每家商店只会卖一种物品，其中第\(i\)家商店的物品单价为\(c_i\)，价值为\(v_i\)，且该商店开张的时间为\(t_i\)。
Byteasar 计划进行\(m\)次购物，其中第\(i\)次购物的时间为\(T_i\)，预算为\(M_i\)。每次购物的时候，Byteasar 会在每家商店购买最多一件物品，当然他也可以选择什么都不买。如果购物的时间早于商店开张的时间，那么显然他无法在这家商店进行购物。
现在 Byteasar 想知道，对于每个计划，他最多能购入总价值多少的物品。请写一个程序，帮助 Byteasar 合理安排购物计划。
注意：每次所花金额不得超过预算，预算也不一定要花完，同时预算不能留给其它计划使用。
按照时间排序，保证能够取得已经开业的商店。
反向背包，记录取得i的价值的物品的最小代价，对于每个询问二分答案。
signed main()
{
poread(n), poread(m);
for(register int i = 1; i <= n; ++i)
poread(mk[i].c), poread(mk[i].v), poread(mk[i].t), mx += mk[i].v;
for(register int i = 1; i <= m; ++i)
poread(sp[i].t), poread(sp[i].m), sp[i].id = i;
sort(mk + 1, mk + 1 + n);
sort(sp + 1, sp + 1 + m);
memset(f, 0x3f, sizeof(f));
f[0] = 0;
for(register int i = 1, k = 0; i <= m; ++i)
{
while(mk[k + 1].t <= sp[i].t && k < n)
{
++k;
for(register int j = mx; j >= mk[k].v; --j)
f[j] = min(f[j], f[j - mk[k].v] + mk[k].c);
for(register int j = mk[k].v ; j >= 1; --j)
f[j] = min(f[j + 1], f[j]);
}
register int l = 0, r = mx, mid, res;
while(l <= r)
{
mid = (l + r) >> 1;
if(f[mid] > sp[i].m)
res = mid, r = mid - 1;
else
l = mid + 1;
}
ans[sp[i].id] = res - 1;
}
for(register int i = 1; i <= m; ++i)
printf("%d\n", ans[i]);
return 0;
}