[Acwing] 4319. 合适数对 hash+算术基本定理

前言

传送门 :

思路

a i ∗ a j = x k a_i*a_j=x^k ai​∗aj​=xk

根据算术基本定理 :
N = p 1 a 1 ∗ p 2 a 2 . . . p n a n N=p_1^{a1}*p_2^{a2}...p_n^{an} N=p1a1​∗p2a2​...pnan​

可以将一个数拆为质因数的次幂的乘积

对于 x k x^k xk
我们将其拆分成
x = p 1 a 1 ∗ p 2 a 2 . . . p k a k x=p_1^{a1}*p_2^{a2}...p_k^{ak} x=p1a1​∗p2a2​...pkak​

显然我们再把k次幂搞上去 , 对于每个$p$的指数都变成了 k的倍数

(啊 这里因为我对 x k x^k xk进行质因数分解,看到$k$的倍数的时候感觉不合乎常理,总算懂了)

因此开始分析

a j = p 1 a 1 ∗ p 2 a 2 . . . p k a k a_j=p_1^{a1}*p_2^{a2}...p_k^{ak} aj​=p1a1​∗p2a2​...pkak​
a i = p 1 b 1 ∗ p 2 b 2 . . . p k b k a_i=p_1^{b1}*p_2^{b2}...p_k^{bk} ai​=p1b1​∗p2b2​...pkbk​
根据上面推出来的
因此对于每一个 a i + b i % k = 0 ( a 这 里 是 指 数 a_i+b_i\%k=0(a这里是指数 ai​+bi​%k=0(a这里是指数

数据范围$100000$,所有数质因子的数量 n l n n ( 1000 − 10000 ) \frac{n}{ln^n} (1000-10000) lnnn​(1000−10000)

但是对于每个数,出现过和其他数不同的质因子很少
$2\ast 3\ast 5\ast 7\ast 11=2310$
$2\ast 3\ast 5\ast 7\ast 11\ast 13=30030$
因此最多只能包含六个质因子
每个数最多只有$6$个质因子,需要补成$k$的倍数

因此这里可以$hash$一个匹配,但是这里可以使用他们的值直接当作$hash$值
x = p 1 t 1 ∗ p 2 t 2 ∗ p 3 t 3 x =p_1^{t1}*p_2^{t2}*p_3^{t3} x=p1t1​∗p2t2​∗p3t3​
y = q 1 r 1 ∗ q 2 r 2 ∗ q 3 r 3 y=q_1^{r1}*q_2^{r2}*q_3^{r3} y=q1r1​∗q2r2​∗q3r3​
如果这两个中但凡出现一个不同那么$xy$都不相同

code

const int N = 100010;int n, m;
int cnt[N];int power(int a, int b)
{LL res = 1;while (b -- ){res *= a;if (res >= N) res = 0;}return res;
}int main()
{scanf("%d%d", &n, &m);LL res = 0;while (n -- ){int x;scanf("%d", &x);LL y = 1, z = 1;for (int i = 2; i * i <= x; i ++ )if (x % i == 0){int s = 0;while (x % i == 0) x /= i, s ++ ;s %= m;if (s) {y *= power(i, s);z *= power(i, m - s);}}/**这一整个过程都是hash**/if (x > 1) y *= x, z *= power(x, m - 1);if (z >= N) z = 0;res += cnt[z];cnt[y] ++ ;}printf("%lld\n", res);return 0;
}

Stl暴力 4483ms

const int N  = 1e5+10;
int a[N];
map<vector<pii>,int> cnt;void solve()
{int n,m;cin>>n>>m;for(int i=1;i<=n;i++) cin>>a[i];ll ans = 0 ;for(int i=1;i<=n;i++){//枚举每一个 a[i]int x = a[i];vector<pii> b,c;for(int j=2;j<=x/j;j++){//筛选质因数 O sqrt(n)int t = 0 ;while(x%j == 0) x/=j,++t;//j^tif(t%m) b.pb({j,t%m});}if(x>1){//分解质因子b.pb({x,1});}c = b;for(auto &[x,y] : c) y = m-y; //ans+= 1ll*cnt[c];cnt[b]++;}cout<<ans<<endl;}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！