problem

对于一个数对(a,b) 如果满足a%ba/b则称这个数对为“好的数对”。 如果 a⩽n,b⩽n那么有多少对数对是“好的数对”呢

1⩽n⩽1e9

pdf题面

Sample Input

5

8

3

65

Sample Output

3

7

1

131

思路1

表面意思 ∑na1∑nb1[a%ba/b] 这里a/b⌊ab⌋

由于aab∗ba%b 可得a(a%b)∗(b1) 那我只要枚举a和它的因子d,凡是满足a=(a%(d−1))∗d 的因子d，d−1即为对应的b。时间复杂度O(nlogn)会TLE

令ta%b 显然t

。对于每一个t累加b的个数nt−1−t即为答案。时间复杂度O(n)会TLE。代码如下

ll ans0;for(int t1;tt){//这时候才有意义 因为ta%b t 再进一步思考为什么要做这个限制呢因为这是b的上限肯定在大于t的情况下才有意义

if((n/t-1)>t)

观察(b1)∗t⩽n 又t

代码示例

#includeusing namespace std;typedef long long ll;int main(){ios::sync_with_stdio(false);ll n;while(cin>>n){ll ans0;for(int t1;t*(t1)思路2

直接对a的因子进行考虑由于因子成对出现完全平方数单独考虑发现以a√为界限右面的因子都有对应的b满足题意

于是考虑求出1~n区间内所有数的因子(出现一次)但时间限制不能去枚举每个a。从反面考虑因子可能情况即1是哪些数的因子2是哪些数的因子3是哪些数的因子…… 即先求出⌊n1⌋⌊n2⌋⌊n3⌋⌊n4⌋......⌊nn⌋

然后ans-3是因为a1 a2时无符合题意而其有3个因子于是减去。

下面两行是考虑完全平方数和t*(t1)两种特殊情况

for(int i2;i*i最后ans/2即为结果右半边

求⌊n1⌋⌊n2⌋⌊n3⌋⌊n4⌋......⌊nn⌋的方法

ans0;int l1;for(;l代码示例

#includeusing namespace std;const int maxn1e9;int n;long long ans0;int main(){while(scanf("%d",EOF){ans0;int l1;for(;l

上一篇：MFC在父对话框中内嵌子对话框
下一篇：没有了