EDUC139 div2 가상
https://codeforces.com/contest/1766
대시보드 – 교육 Codeforces 라운드 139(등급 2부) – Codeforces
codeforces.com
ㅏ.
1<=x<=n 범위의 모든 x에 대해 하나의 숫자만 0이 아닌 주어진 n에 대한 x의 수입니다.
각 숫자에 9를 더하면 됩니다. 그 숫자가 가장 중요한 숫자라면 그 숫자를 더하세요.
비.
두 가지 작업이 있습니다.
1. 하위 문자열을 복사하여 붙여넣고 끝에 넣습니다.
2. 임의의 문자 뒤에 넣습니다.
최대 n-1 번 수행하여 주어진 문자열과 동일하게 만들 수 있습니까?
2개의 연산만 적용하면 n번 수행이 가능합니다.
따라서 하나의 연산에 하나의 연산만 적용할 수 있다면 n-1 이하도 가능합니다.
따라서 인접한 두 문자열을 저장하고 이전 두 문자열이 이미 저장되었는지 여부를 판단합니다.
씨.
(2, M)의 그리드에는 W 블록과 B 블록이 있습니다.
B로만 이동 가능
문제는 인접한 블록을 이동해야만 모든 B에 도달할 수 있다는 것입니다.
어떤 지점을 왼쪽에서 오른쪽으로 이동해 보겠습니다. 이 경우 해당 상태에서 이동하는 방향은 하나뿐입니다.
따라서 처음 두 상태에 대해서만 bfs를 실행하면 됩니다.
디.
질문을 읽을 때 gcd 유클리드 알고리즘이 생각났는데 아무리 봐도 알 수가 없었다.
그래도 최대공약수 문제이기 때문에 두 수의 공약수와 관련이 있지 않을까 해서 집중적으로 알아봤습니다.
나는 그것이 차이와 관련이 있다는 것을 발견했고 그것이 차이의 배수여야 한다고 생각했습니다.
예를 들면 10009와 20000이고 답은 97이지만 두 숫자의 차이는 9991이므로 10088은 9991의 배수가 아닙니다.
9991을 분해할 때 97이 주요 인자 중 하나이고 이것을 알아내기 위해 사용합니다.
의식을 거행하다
A+D, A에 1을 더할 때 먼저 같은 수로 나누어떨어져야 합니다.
첫째, D는 나누어질 수 있어야 하고, A + K는 나누어져야 합니다.
A+K는 D의 소인수 배수여야 합니다.
그러나 여기서는 D의 가장 작은 소인수뿐만 아니라 D의 모든 소인수도 연구해야 합니다.
sqrt(N) 소인수 분해만 하면
O(N*sqrt(10^7)*log(10^7))의 시간 복잡도
이를 줄이기 위해 선형 체를 사용하여 10^7에 있는 모든 숫자의 소인수를 찾아 처리할 수 있습니다.