문제 링크
b ⋅ gcd ( a , b ) b \cdot \gcd(a, b) b ⋅ g cd( a , b ) a + b a+b a + b ( a , b ) (a, b) ( a , b )
g c d ( a , b ) = g gcd(a, b) = g g c d ( a , b ) = g a ′ , b ′ a',\, b' a ′ , b ′ a = a ′ g , b = b ′ g , gcd ( a ′ , b ′ ) = 1 a = a'g,\, b = b'g,\, \gcd(a', b') = 1 a = a ′ g , b = b ′ g , g cd( a ′ , b ′ ) = 1
a + b ∣ b g ⇔ ( a ′ + b ′ ) g ∣ b ′ g 2 ⇔ ( a ′ + b ′ ) ∣ b ′ g ⇔ ( a ′ + b ′ ) ∣ g ( ∵ gcd ( a ′ + b ′ , b ′ ) = 1 ) \begin{aligned} &a+b \, \vert \, bg \\ \Leftrightarrow \; &(a'+b')g \, \vert \, b'g^2 \\ \Leftrightarrow \; &(a'+b') \, \vert \, b'g \\ \Leftrightarrow \; &(a'+b') \, \vert \, g \; (\because \gcd(a'+b', b') = 1) \end{aligned} ⇔ ⇔ ⇔ a + b ∣ b g ( a ′ + b ′ ) g ∣ b ′ g 2 ( a ′ + b ′ ) ∣ b ′ g ( a ′ + b ′ ) ∣ g ( ∵ g cd( a ′ + b ′ , b ′ ) = 1 ) 를 얻을 수 있습니다.
문제 조건까지 종합 해보면 a ′ + b ′ = d a'+b' = d a ′ + b ′ = d
( b ′ + 1 ≤ d ≤ ⌊ n g ⌋ + b ′ ) ∧ ( d ∣ g ) ∧ ( gcd ( d , b ′ ) = 1 ) \left( b' + 1 \leq d \leq \lfloor \frac n g \rfloor + b' \right) \, \wedge \, \left( d \, | \, g \right) \, \wedge \, \left( \gcd(d, b') = 1 \right) ( b ′ + 1 ≤ d ≤ ⌊ g n ⌋ + b ′ ) ∧ ( d ∣ g ) ∧ ( g cd( d , b ′ ) = 1 ) 1 ≤ b ′ ≤ ⌊ m g ⌋ 1 \leq b' \leq \lfloor \frac m g \rfloor 1 ≤ b ′ ≤ ⌊ g m ⌋ max ( 1 , d − ⌊ n g ⌋ ) ≤ b ′ ≤ min ( d − 1 , ⌊ m g ⌋ ) \max(1, d - \lfloor \frac n g \rfloor) \leq b' \leq \min(d-1, \lfloor \frac m g \rfloor) max ( 1 , d − ⌊ g n ⌋ ) ≤ b ′ ≤ min ( d − 1 , ⌊ g m ⌋ )
즉, g c d ( a , b ) = g gcd(a, b) = g g c d ( a , b ) = g ( a , b ) (a, b) ( a , b )
∑ d ∣ g ∣ { x ∣ gcd ( d , x ) = 1 ∧ max ( 1 , d − ⌊ n g ⌋ ) ≤ x ≤ min ( d − 1 , ⌊ m g ⌋ ) } ∣ \sum_{d \, | \, g}{\left\lvert\{x|\gcd(d, x) = 1 \wedge \max(1, d - \lfloor \frac n g \rfloor) \leq x \leq \min(d-1, \lfloor \frac m g \rfloor) \}\right\rvert} d ∣ g ∑ ∣ ∣ ∣ ∣ ∣ { x ∣ g cd( d , x ) = 1 ∧ max ( 1 , d − ⌊ g n ⌋ ) ≤ x ≤ min ( d − 1 , ⌊ g m ⌋ ) } ∣ ∣ ∣ ∣ ∣ 문제에서 구해야 하는 순서쌍의 갯수는 아래와 같습니다.
∑ g = 1 min ( n , m ) ∑ d ∣ g ∣ { x ∣ gcd ( d , x ) = 1 ∧ max ( 1 , d − ⌊ n g ⌋ ) ≤ x ≤ min ( d − 1 , ⌊ m g ⌋ ) } ∣ \displaystyle\sum_{g = 1}^{\min(n, m)}{\sum_{d \, | \, g}{\left\lvert\{x|\gcd(d, x) = 1 \wedge \max(1, d - \lfloor \frac n g \rfloor) \leq x \leq \min(d-1, \lfloor \frac m g \rfloor) \}\right\rvert}} g = 1 ∑ m i n ( n , m ) d ∣ g ∑ ∣ ∣ ∣ ∣ ∣ { x ∣ g cd( d , x ) = 1 ∧ max ( 1 , d − ⌊ g n ⌋ ) ≤ x ≤ min ( d − 1 , ⌊ g m ⌋ ) } ∣ ∣ ∣ ∣ ∣ 시그마 부분을 살짝 바꾸면 아래와 같이 바꿀 수 있습니다.
∑ d = 1 min ( n , m ) ∑ d ∣ g ∣ { x ∣ gcd ( d , x ) = 1 ∧ max ( 1 , d − ⌊ n g ⌋ ) ≤ x ≤ min ( d − 1 , ⌊ m g ⌋ ) } ∣ \displaystyle\sum_{d = 1}^{\min(n, m)}{\sum_{d \, | \, g}{\left\lvert\{x|\gcd(d, x) = 1 \wedge \max(1, d - \lfloor \frac n g \rfloor) \leq x \leq \min(d-1, \lfloor \frac m g \rfloor) \}\right\rvert}} d = 1 ∑ m i n ( n , m ) d ∣ g ∑ ∣ ∣ ∣ ∣ ∣ { x ∣ g cd( d , x ) = 1 ∧ max ( 1 , d − ⌊ g n ⌋ ) ≤ x ≤ min ( d − 1 , ⌊ g m ⌋ ) } ∣ ∣ ∣ ∣ ∣ 이제 위 식의 값을 구해야 합니다. 잘 보시면 g g g max ( 1 , d − ⌊ n g ⌋ ) \max(1, d - \lfloor \frac n g \rfloor) max ( 1 , d − ⌊ g n ⌋ ) min ( d − 1 , ⌊ m g ⌋ ) \min(d-1, \lfloor \frac m g \rfloor) min ( d − 1 , ⌊ g m ⌋ ) g = d g = d g = d gcd ( d , x ) = 1 \gcd(d, x) = 1 g cd( d , x ) = 1 x x x g g g
위 방법의 시간 복잡도는 아래와 같습니다. TLE를 안 받을 수 있을만큼 충분히 빠를까요?
O ( log ( min ( n , m ) ) ⋅ ∑ d = 1 min ( n , m ) max ( 0 , min ( d − 1 , ⌊ m d ⌋ ) − max ( 1 , d − ⌊ n d ⌋ ) ) ) O\left(\log(\min(n, m)) \cdot \displaystyle\sum_{d = 1}^{\min(n, m)}{\max\left(0, \min(d-1, \lfloor \frac m d \rfloor)-\max(1, d - \lfloor \frac n d \rfloor)\right)}\right) O ⎝ ⎜ ⎛ log ( min ( n , m ) ) ⋅ d = 1 ∑ m i n ( n , m ) max ( 0 , min ( d − 1 , ⌊ d m ⌋ ) − max ( 1 , d − ⌊ d n ⌋ ) ) ⎠ ⎟ ⎞
조금 더 간단하게 표현해 보겠습니다. 잘 보시면 d d d n ≤ d 2 n \leq d^2 n ≤ d 2 m ≤ d 2 m \leq d^2 m ≤ d 2 min \min min max \max max d ≥ m + n d \geq \sqrt{m+n} d ≥ m + n min ( d − 1 , ⌊ m d ⌋ ) − max ( 1 , d − ⌊ n d ⌋ ) \min(d-1, \lfloor \frac m d \rfloor)-\max(1, d - \lfloor \frac n d \rfloor) min ( d − 1 , ⌊ d m ⌋ ) − max ( 1 , d − ⌊ d n ⌋ )
즉, 시간 복잡도를 간단하게 표현하면 아래와 같이 됩니다.
O ( log ( m + n ) ⋅ ( ∑ d = 1 max ( n , m ) d + ∑ d = max ( n , m ) + 1 n + m 2 ( n + m ) − d ) ) → O ( log ( m + n ) ⋅ ( ∑ d = 1 n + m d + ∑ d = n + m + 1 2 ( n + m ) 2 ( n + m ) − d ) ) → O ( ( n + m ) 2 log ( m + n ) ) → O ( ( n + m ) log ( m + n ) ) \begin{aligned} &O\left(\log(m+n) \cdot \left(\displaystyle\sum_{d = 1}^{\max(\sqrt{n}, \sqrt{m})}{d} + \displaystyle\sum_{d=\max(\sqrt{n}, \sqrt{m})+1}^{\sqrt{n+m}}{2(\sqrt{n}+\sqrt{m})-d} \right) \right) \\\\ \rightarrow \, &O\left(\log(m+n) \cdot \left(\displaystyle\sum_{d = 1}^{\sqrt{n}+\sqrt{m}}{d} + \displaystyle\sum_{d=\sqrt{n}+\sqrt{m}+1}^{2(\sqrt{n}+\sqrt{m})}{2(\sqrt{n}+\sqrt{m})-d}\right) \right) \\\\ \rightarrow \, &O((\sqrt{n}+\sqrt{m})^2\log(m+n)) \\\\ \rightarrow \, &O((n+m)\log(m+n)) \end{aligned} → → → O ⎝ ⎜ ⎛ log ( m + n ) ⋅ ⎝ ⎜ ⎛ d = 1 ∑ m a x ( n , m ) d + d = m a x ( n , m ) + 1 ∑ n + m 2 ( n + m ) − d ⎠ ⎟ ⎞ ⎠ ⎟ ⎞ O ⎝ ⎜ ⎛ log ( m + n ) ⋅ ⎝ ⎜ ⎛ d = 1 ∑ n + m d + d = n + m + 1 ∑ 2 ( n + m ) 2 ( n + m ) − d ⎠ ⎟ ⎞ ⎠ ⎟ ⎞ O ( ( n + m ) 2 log ( m + n ) ) O ( ( n + m ) log ( m + n ) ) n n n m m m
pseudo code는 다음과 같습니다.
ans < - 0
loop d from 1 to min ( n, m) {
cur < - 0
loop g from d to min ( n, m) step d {
if g equal d {
l, r < - max ( 1 , d- n/ d) , min ( d- 1 , m/ d)
cur < - number of x such that gcd ( d, x) == 1 and l <= x <= r
ans += cur
}
else {
nl, nr < - max ( 1 , d- n/ d) , min ( d- 1 , m/ d)
cur -= number of x such that gcd ( d, x) == 1 and ( l <= x < nl or nr < x <= r)
ans += cur
l, r < - nl, nr
}
if l > r {
break
}
}
}
print ans
