레이팅 미적용설명
모든 양의 정수 \(x\)에 대해 함수 \(f(x)\)는 다음과 같이 정의된다.
- \(x\)에 \(0\) 또는 \(1\)이 아닌 자릿수가 하나라도 있으면, \(x\)의 각 자릿수에 대해 그 자릿수가 홀수이면 \(1\)로, 아니면 \(0\)으로 바꾸고 \(x\)를 반환한다.
- 그렇지 않으면 \(x-1\)을 반환한다.
\(x\) (\(1 \leq x < 10^{2\cdot 10^5}\))의 값이 주어졌을 때, \(x\)가 \(0\)이 될 때까지 \(f\)를 \(x\)에 몇 번 적용해야 하는지 구하시오. 이 수는 매우 클 수 있으므로 \(10^9+7\)로 나눈 나머지를 출력한다.
문제 제공: Aidan Bai
제약
채점 방식
- 입력 3-5: \(T\le 2000\), \(x< 10^{9}\)
- 입력 6-7: \(x<10^{18}\)
- 입력 8-9: \(x<10^{60}\)
- 입력 10-12: 추가 제약 조건이 없다.
문제 제공: Aidan Bai
입력 형식
첫째 줄에 독립적인 테스트의 수 \(T\) (\(1\le T\le 10^5\))가 주어진다.
다음 \(T\)개의 줄 각각에 숫자 0-9로만 이루어지고 앞자리 0이 없는 양의 정수 \(x\)가 주어진다.
모든 입력 정수의 총 자릿수는 \(10^6\)을 넘지 않음이 보장된다.
출력 형식
각 테스트 케이스마다, 적용 횟수를 \(10^9+7\)로 나눈 나머지를 한 줄에 하나씩 출력한다.
예제 1
입력
2
24680
210출력
1
4설명
First test: \(x\) becomes zero after one operation.
Second test: \(f(x)=10, f^2(x)=9, f^3(x)=1, f^4(x)=0\)
예제 2
입력
1
1234567890123456789012345678901234567890출력
511620083문제 정보
riseoj 작성
출처 올림피아드 > USACO > 2025-2026 > Third Contest > Bronze
태그