P12174 [蓝桥杯 2025 省 Python B] A · B Problem

题目描述

设有两个二维向量 $\overrightarrow{A}(X_A,Y_A),\overrightarrow{B}(X_B,Y_B)$。给定 $L$，求 $(X_A,Y_A),(X_B,Y_B)$ 有多少种不同的取值，使得：

1. $X_A,Y_A,X_B,Y_B$ 均为正整数；
2. $\overrightarrow{A}\cdot \overrightarrow{B}\le L$，其中 $\overrightarrow{A}\cdot \overrightarrow{B}$ 表示 $\overrightarrow{A},\overrightarrow{B}$ 的内积，即 $X_A\cdot X_B+Y_A\cdot Y_B$。

输入格式

输入的第一行包含一个正整数 $L$，表示题目描述中的限制条件。

输出格式

输出一行包含一个整数表示答案。

输入输出样例 #1

输入 #1

2

输出 #1

1

输入输出样例 #2

输入 #2

3

输出 #2

5

说明/提示

评测用例规模与约定

• 对于 $40\%$ 的评测用例，$L\le 50$；
• 对于 $80\%$ 的评测用例，$L\le 5000$；
• 对于所有评测用例，$1\le L\le 2^{20}$。

C++实现

#include<bits/stdc++.h>
using namespace std;
const int mxn=1.05e6+2;//2^20
int f[mxn],n;//f[i]=d(i)
inline void pre(int x){
	bool fl=0;
	for(int i=1;i*i<=x;i++){
		f[x]+=!(x%i);
		if(i*i==x) fl=1;
	}
	f[x]<<=1;
	f[x]-=(fl);
}
unsigned long long ans;
int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;i++) pre(i);
	for(int i=1;i<=n;i++){
		for(int j=1;j<i;j++){
			ans+=f[j]*f[i-j];
		}
	}
	cout<<ans<<endl;
}

后续

接下来我会不断用C++来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现，记录日常的编程生活、比赛心得，感兴趣的请关注，我后续将继续分享相关内容