수론 + 이분 (계승 접미사 0 의 개수) - Trailing Zeroes (III) - LightOJ 1138

수론 + 이분 (계승 접미사 0 의 개수) - Trailing Zeroes (III) - LightOJ 1138
제목:
n 의 곱 하기 끝부분 에 q 개의 연속 0 이 있 습 니 다. 지금 q 를 드 리 겠 습 니 다. 조건 을 만족 시 키 는 n 을 계산 하 십시오. 만약 여러 개의 n 이 조건 을 만족 시 키 면 가장 작은 것 을 출력 하면 됩 니 다.n 의 곱 하기 끝부분 에 q 개의 연속 0 이 있 습 니 다. 지금 q 를 드 리 겠 습 니 다. 조건 을 만족 시 키 는 n 을 계산 하 십시오. 만약 여러 개의 n 이 조건 을 만족 시 키 면 가장 작은 것 을 출력 하면 됩 니 다.n 의 곱 하기 끝부분 에 q 개의 연속 0 이 있 습 니 다. 지금 q 를 드 리 겠 습 니 다. 조건 을 만족 시 키 는 n 을 계산 하 십시오. 만약 여러 개의 n 이 조건 을 만족 시 키 면 가장 작은 것 을 출력 하면 됩 니 다.
Input
T (T ≤ 10000) 를 입력 하여 샘플 수량 을 표시 합 니 다.
샘플 마다 q 를 입력 하 십시오.(1 ≤ q ≤ 100,000,000)
Output
모든 사례 에 대해 출력 만족 조건 의 최소 n 을 만족 시 키 지 않 으 면 'impossible' 을 출력 합 니 다.
Sample Input

3
1
2
5

Sample Output

Case 1: 5
Case 2: 10
Case 3: impossible

T i m e   l i m i t : 2000 m s , M e m o r y   l i m i t : 32768 k B Time\ limit:2000 ms,Memory \ limit:32768 kB Time limit:2000ms,Memory limit:32768kB
분석:
각 수의 접미사 0 의 개 수 는 그 질량 인자 2 와 5 의 지수 에 달 려 있다.각 수의 접미사 0 의 개 수 는 그 질량 인자 2 와 5 의 지수 에 달 려 있다.각 수의 접미사 0 의 개 수 는 그 질량 인자 2 와 5 의 지수 에 달 려 있다.
곱 하기 접미사 0 의 개 수 는 질 인자 5 의 지수 에 달 려 있 는데 5 의 지 수 는 항상 2 와 같은 지수 보다 크기 때문이다.곱 하기 접미사 0 의 개 수 는 질 인자 5 의 지수 에 달 려 있 는데 5 의 지 수 는 항상 2 와 같은 지수 보다 크기 때문이다.곱 하기 접미사 0 의 개 수 는 질 인자 5 의 지수 에 달 려 있 는데 5 의 지 수 는 항상 2 와 같은 지수 보다 크기 때문이다.
답 은 단조 로 움 을 만족 시 키 고 최소 치 를 구하 기 때문에 우 리 는 직접 2 분 의 답 을 구 할 수 있다.답 은 단조 로 움 을 만족 시 키 고 최소 치 를 구하 기 때문에 우 리 는 직접 2 분 의 답 을 구 할 수 있다.답 은 단조 로 움 을 만족 시 키 고 최소 치 를 구하 기 때문에 우 리 는 직접 2 분 의 답 을 구 할 수 있다.
각 2 분 의 답안 m i d 에 대해 우 리 는 m i d 의 곱셈, 질 인자 5 의 지수, c a l (m i d) 이 q 보다 큰 지 판단 한다.각 2 분 의 답안 mid 에 대해 우 리 는 mid 의 곱셈, 질 인자 5 의 지수, cal (mid) 이 q 보다 큰 지 판단 한다.각 2 분 의 답안 mid 에 대해 우 리 는 mid 의 곱셈, 질 인자 5 의 지수, cal (mid) 이 q 보다 큰 지 판단 한다.
2 점 만족 m i d!의 인자 5 의 지수, c a l (m i d) ≥ q 의 최소 m i d, 2 점 만족 mid!의 인자 5 의 지수, cal (mid) ≥ q 의 최소 mid, 2 점 만족 mid!의 인자 5 의 지수, cal (mid) ≥ q 의 최소 mid,
그리고 우 리 는 c a l (m i d) = q 가 성립 되 는 지 를 보면 된다.그리고 우 리 는 cal (mid) = q 가 성립 되 는 지 를 보면 된다.그리고 우 리 는 cal (mid) = q 가 성립 되 는 지 를 보면 된다.
주의:
2 분 의 경계 l = 5, 오른쪽 경계 r: 2 분 의 경계 l = 5 를 고려 하고 오른쪽 경계 r: 2 분 의 경계 l = 5 를 고려 하 며 오른쪽 경계 r:
기껏해야 109 개의 접미사 0, 즉 인자 5 의 지 수 는 0.9 이 고 기껏해야 10 ^ 9 개의 접미사 0, 즉 인자 5 의 지 수 는 10 ^ 9 이 며, 기껏해야 109 개의 접미사 0, 즉 인자 5 의 지 수 는 109 이다.
10 간격 마다 최소 두 개의 수의 인자 에 51 이 포함 되 어 있 고 10 간격 마다 최소 두 개의 인자 에 5 ^ 1 이 포함 되 어 있 으 며 10 간격 마다 최소 두 개의 인자 에 51 이 포함 되 어 있 습 니 다.
그러면× 2 = 1, 0, 9, r = 5× 1 0 9, 오른쪽 경계 가 5 를 넘 지 않 는 다 고 대충 짐작 할 수 있다.× 1 0 9 。 \ frac {r} {10}×2 = 10 ^ 9, r = 5 획득 가능×10 ^ 9, 오른쪽 경계 가 5 를 초과 하지 않 는 다 고 대충 추정 할 수 있 습 니 다.×10^9。 즉 10r×2 = 109, r = 5 획득 가능×109, 오른쪽 경계 가 5 를 초과 하지 않 는 다 고 대충 예측 할 수 있다.×109。
코드:

#include
#include
#include
#include
#include

#define ll long long

using namespace std;

ll cal(ll n)
{
    ll s=0;
    for(ll i=n;i;i/=5) s+=i/5;
    return s;
}

int main()
{
    int T; cin>>T;
    for(int t=1;t<=T;t++)
    {
        int q; scanf("%d",&q);
        ll l=5, r=1e10;
        while(l<r)
        {
            ll mid=l+r>>1;
            if(cal(mid)>=q) r=mid;
            else l=mid+1;
        }
        
        printf("Case %d: ",t);
        if(cal(l)!=q) puts("impossible");
        else printf("%lld
",l);
    }
    return 0;
}