Atcoder abc339

發表於 更新於 分類於 ， Disqus： 文章字數： 257 所需閱讀時間 ≈ 1 分鐘
F(随机性)

https://atcoder.jp/contests/abc339

F - Product Equality

n个数字a[n], 问有多少个有序对(i,j,k)满足

A[i]*A[j]=A[k]

n 1000

$a[i] \in [0,10^{10}]$

2s

1024mb

我的思路

光是 枚举 (i,j) 那么也是 n^2了，那么乘法和对比就要足够快, 然而最快的就算ntt，也是 (长度 log(长度)) 会tle

一个想法 是 通过减少比较范围，但如果正好 一半长度 [len/2] 一半长度[len]

第二个想法是 选取一些 质数p,然后通过类似hash的想法来完成

a[i] * a[j] == a[k]

那么 (a[i] % p)*(a[j] % p) % p== a[k] %p

没有任何确定性算法

然后就是 十进制压8位，但这样也只是降低到 int[125] x int[125]

n的个数没有减少

题解

好家伙, 真的就随机20个数, 然后 就mod校验

代码

略

总结

F: 卡蓝题了,我吐了

但这种基于“概率”感觉的方法，总给我数学上的不适感。哎