구해야 하는 것은 $$\sum_{(a,b)}\sum_{(c,d)}\sum_{(e,f)}[ \gcd(Y_{a,b},Y_{c,d},Y_{e,f})=1]$$ 이다. 뫼비우스 역변환을 이용하면 $$\sum_{s=1}^{359999}\mu(s)\sum_{(a,b)}\sum_{(c,d)}\sum_{(e,f)}[s|Y_{a,b}][s|Y_{c,d}][s|Y_{e,f}]$$ 이다. 그럼 우리는 $Y_{a,b}$이 각각 어떤 값을 가지고 얼마나 많은 중복이 일어나는지 세면 답을 구할 수 있다. 문제에서 $Y_{a,b}=X_{a}\times X_{b}\pmod{359999}$이다. 즉, $X_{a}$들의 범위는 $0~359998$이라 생각해도 무방하다. 특히, $359999 = 599 \times 601$로 CRT를 이용..

문제를 접근하는 방법은 각 소수$q$에 대해서 $ax^{2}+bx+c \equiv 0\pmod{q}$를 만족하는 $x$를 찾는 것이다. 그럼 소수 $q$는 어느 범위까지 검사해야할까? 문제에서 구하라고 하는 것은 주어진 곱을 나누는 제곱수이다. 적절한 커팅을 이용해서 확인해 봐야 하는 소수의 개수를 줄이도록 하자. $(an^{2}+bn+c)^{1/3}$보다 작은 소수들을 모두 검사한다고 하자. 어떤 수 $x$가 어떤 자연수 $k$에 대해서 $ax^{2}+bx+c=p\cdot k$를 만족한다고 하자, 그럼 에라토스테네스의 체처럼 $(an^{2}+bn+c)^{1/3}$ 보다 작은 소수들로 각 $p(x)$들을 나누자. 남은 $p(x)$들은 $(an^{2}+bn+c)^{1/3}$보다 큰 소수 2개의 곱으로 이루..

굉장히 멋진 아이디어를 사용하는 문제!! 정말 멋진 문제!! 우리는 Dirichlet convolution을 modulo p에 대해서 계산한다는 것을 관찰하자. 이때 다음을 생각한다. Lemma. 모든 산술 함수 $f:\{1,\cdots,n\}\rightarrow \mathbb{Z}$에 대해서 $2^{p}>n$이면 $f^{p}\equiv \epsilon \pmod{p}$이다. Proof. 함수 $f^{p}$는 다음과 같다. $$f^{p}(n)=\sum_{a_{1}\cdots a_{p}=n}f(a_{1})\cdots f(a_{p})$$ 이때 summation 아래의 조건을 만족하는 튜플 $(a_{1},\cdots,a_{p})$를 고려하자. 하나의 튜플을 찾았다면 permutation을 통해 다른 튜플을 찾..

$\newcommand{\Z}{\mathbb{Z}}$ $\newcommand{\N}{\mathbb{N}}$ $\newcommand{\gang}[1]{\langle #1 \rangle}$ We have to calculate the number of the possible value form of $x^{p}+q \pmod{n}$. Lemma 1. There exists a bijection between $\{x^{p}+q\pmod{n}\}$ and $\{x^{p}\pmod{n}\}$. Proof. For convenience, let each set be $A,B$ resp. Construct a map $\phi:A\rightarrow B$ with $\phi(\overline{a})=\overlin..

이 문제는 $\{1,\cdots,n\}$까지의 수 중에서 $\gcd(i,j)>1$을 만족하는 $(i,j)$ 쌍들을 최대한 많이 만들고 쌍을 만들 수 없는 경우 자기 자신이 쌍이 될 때 최소의 쌍의 개수가 몇 개인지 구하는 것이다. 우리는 $p>N/2$이면 $p$는 쌍을 만들 수 없다는 사실을 안다. 다음과 같은 과정을 생각해보자. $\{1\cdots n\}$에서 쌍이 완벽히 지어졌다 가정하자. 우리는 $n+1$을 저 집합에 추가하고 최적의 쌍을 얻어낼 것이다. 0. $n+1$이 소수이다. - $(n+1,n+1)$을 쌍으로 한다. 1. $\{1\cdots n\}$ 중에서 짝지어지지 않은 소수 $p$가 존재하여 $p|n+1$이다. - $(p,n+1)$을 쌍으로 한다. 2. $\{1\cdots n\}$에서 $..

주어진 식을 다음과 같이 변형하자. 이때 $x>y$ 임에 주의하자. $$(x-y)^{2}+x^{2}+n=(x+y)^{2}$$ $$n=x(4y-x)$$ 여기서 $x|n$을 얻는다. 또 $$4|(\frac{n}{x}+x)=4y$$ $x>y$조건에서 다음을 얻는다. \[y=\frac{\frac{n}{x}+x}{4}