专栏文章

题解：AT_agc047_a [AGC047A] Integer Product

RRioFutaba
AT_agc047_a题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@miq7rn0r
此快照首次捕获于
2025/12/04 00:20
3 个月前
此快照最后确认于
2025/12/04 00:20
3 个月前
查看原文

题意

给定 nn 个实数 A1A_1 到 AnA_n，求有多少对 i,ji,j（i<ji<j）使得 Ai×AjA_i \times A_j 是整数。
1≤n≤2×1051 \le n \le 2 \times 10^5，0<Ai<1040 < A_i <10^4。AiA_i 小数点后不超过 99 位。

解法

显然，Ai×109A_i \times 10^9 是一个整数。如果 Ai×AjA_i \times A_j 是整数，那么 (Ai×109)×(Aj×109)(A_i \times 10^9) \times (A_j \times 10^9) 后面得有 1818 个 00，也就是它是 10810^8 的倍数。
如果一个数是 10810^8 的倍数，那么它质因子 22 的个数和 55 的个数都 ≥18\geq 18。
先把每个 AiA_i 都乘上 10910^9，计算出它质因子 22 和 55 的个数。再暴力判断之前有多少个数和它乘在一起符号要求。
CPP
#include <bits/stdc++.h>
using namespace std;

#define db long double
#define ll long long
const int maxn=2e5+5;
int n;
ll ans,cnt[50][20];//cnt[i][j] 表示质因子2的个数为i，5的个数为j的数的个数
db a[maxn];
int main(){
	cin >> n;
	for(int i=1;i<=n;i++){
		scanf("%Le",&a[i]);
		int c2=0,c5=0;
		ll x=round(a[i]*1e9);//round一下，不然精度会爆炸
		while(!(x%2)) x/=2,c2++;
		while(!(x%5)) x/=5,c5++;//计算
		for(int j=18-c2;j<50;j++)
			for(int k=18-c5;k<20;k++)
				ans+=cnt[j][k];
		cnt[c2][c5]++;
	}
	printf("%lld\n",ans);
	return 0;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...