[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 p p的指数都变成了 k的倍数

(啊 这里因为我对 x k x^k xk进行质因数分解,看到 k k 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 100000 100000,所有数质因子的数量 n l n n ( 1000 − 10000 ) \frac{n}{ln^n} (1000-10000) lnnn​(1000−10000)

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

因此这里可以 h a s h hash hash一个匹配,但是这里可以使用他们的值直接当作 h a s h 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​ 如果这两个中但凡出现一个不同那么 x y xy 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  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 cnt;

void solve()
{
	int n,m;cin>>n>>m;
	for(int i=1;i>a[i];
	
	ll ans = 0 ;
	for(int i=1;i