【今日の精進】AGC003D - Anticube

毎日格上の問題を倒すやつの43日目です。

問題リンク

atcoder.jp

問題概要

数列が与えられるよ。

選んだ2数の積が立方数にならないように最大限選んだときの個数を求めてね。

解説

明らかに筋が悪いですがG - Cubic?みたいな感じで解きます。

数を素因数ごとにハッシュをつくることで、立方数になるハッシュの組はひとつだけになります。

そのため、そのペアの多く選べる方からとればいいです。

もともと立方数のものは1個しか選べないことに注意しましょう。

提出コード

from random import randint
from math import gcd
from collections import Counter

def is_prime(n):
    if n%2==0:
        return n==2
    if n==1:
        return False
    d=n-1
    s=0
    while d%2==0:
        d=d//2
        s+=1
    a=[2,7,61,325,9375,28178,450775,9780504,1795265022]
    for i in a:
        if i>=n:
            break
        now=pow(i,d,n)
        if now!=1:
            comp=True
            for j in range(s):
                if now==n-1:
                    comp=False
                    break
                now=(now*now)%n
            if comp:
                return False
    return True

def prime_fact(n):
    ret={}
    for i in range(2,100):
        while n%i==0:
            if i in ret:
                ret[i]+=1
            else:
                ret[i]=1
            n//=i
    if n==1:
        return ret
    calc=[n]
    while len(calc)>0:
        n=calc.pop()
        while not(is_prime(n)):
            x=randint(0,n-1)
            plus=randint(1,n-1)
            y=x
            i=1
            while True:
                x=(x*x+plus)%n
                y=(y*y+plus)%n
                y=(y*y+plus)%n
                d=gcd(abs(x-y),n)
                if d==1:
                    i+=1
                elif d==n or d==0:
                    break
                else:
                    if is_prime(d):
                        if d in ret:
                            ret[d]+=1
                        else:
                            ret[d]=1
                    else:
                        calc.append(d)
                    n=n//d
                    break
        if n in ret:
            ret[n]+=1
        else:
            ret[n]=1
    return ret

N=int(input())
s=[prime_fact(int(input())) for i in range(N)]
a={}
b={}
lhash=[]
pairs=set()
for i in s:
    lnow=0
    rnow=0
    for j in i:
        if j not in a:
            a[j]=randint(0,1<<64-1)
            b[j]=randint(0,1<<64-1)
        if i[j]%3>=1:
            lnow^=a[j]
            rnow^=a[j]^b[j]
        if i[j]%3==2:
            lnow^=b[j]
            rnow^=b[j]
    lhash.append(lnow)
    pairs.add((min(lnow,rnow),max(lnow,rnow)))
cnt=Counter(lhash)
ans=0
for l,r in pairs:
    if l==0:
        ans+=1
        continue
    ans+=max(cnt[l],cnt[r])
print(ans)

Submission #47143750 - AtCoder Grand Contest 003

感想

明日からジャンルが偏るかもしれないらしい