我正在这样做competetive programming task,尽管我认为我有一个渐近最优的解决方案,但仍然超出了时间限制。您需要注册一个帐户才能查看问题说明并提交,所以我将在这里重新声明:
给定范围[L,R],找到该范围内具有奇数个奇数除数的整数的数量。
约束为1
示例:
[1,18]
的解决方案是7,因为在该范围内有7个具有奇数除数的数字:
1 - (1)
2 - (1,2)
4 - (1,2,4)
8 - (1,4,8)
9 - (1,3,9)
16 - (1,8,16)
18 - (1,6,9,18)
我的代码和想法:
我们知道除数成对出现,因此任何具有奇数除数的奇数都必须是平方数。除数为奇数的任何偶数都必须具有除数为奇数的奇数“基数”,而对于此“基数”,它必须像前面讨论的那样为平方数。
本质上,我们正在寻找O^2 * 2^N
形式的数字,其中O
是一些奇数。我将[L,R]
的解决方案视为[1,R] - [1,L)
,然后遍历所有2^N
并获得可容纳该数字的O
数。
# include <bits/stdc++.h>
using namespace std;
typedef long long ll;
// number of numbers matching criteria on [1,n]
ll n_under(ll n){
ll res = 0;
while(n){
res += (sqrt(n) + 1ll)/2ll;
n /= 2ll;
}
return res;
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int q;
cin >> q;
for(int i = 1; i <= q; ++i){
ll l,r;
cin >> l >> r;
cout << "Case " << i << ": " << (n_under(r) - n_under(l - 1)) << endl;
}
return 0;
}
我在第一个测试集中获得TLE,我不确定为什么。我正在寻找任何渐近改进或恒定因子优化。