SDUT 2021 summer team contest 8th

Half Nice Years

题目大意：

有n个区间[L,R],找出每个区间满足下列条件的最大的数：

  1. 将该数平分成两部分，如果该数的位数是奇数则让右侧部分比左侧部分多一位，如123456分成123和456两部分，12345分成12和345两部分，我们把这两部分分别叫pre和past。
  2. 使得这两部分的最大公约数大于1.

思路：

按是否为素数分情况讨论

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
/*
    Kininged_7
*/
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <cstdio>
#include <iostream>
#include <map>
#include <set>
#include <stack>
#include <string>
#include <vector>
#include <queue>
#include <unordered_map>
#include <unordered_set>
#define endl '\n'
#define m0(a) memset(a,0,sizeof a)
#define minf(a) memset(a,0x3f,sizeof a)
#define mcf(a) memset(a,0xcf,sizeof a)
using namespace std;

typedef long long ll;
typedef double ff;
typedef pair<int,int> PII;
typedef pair<double,double> PDD;
const int N = 1e7 + 7;
int v[N];
bool vv[N];
int prime[N],tot;
int n,m;

int num(ll x) {
    int cnt = 0;
    while (x) { cnt ++; x /= 10;}
    return cnt;
}

ll MOD(ll x) {
    ll ans = 1;
    while (x--) ans *= 10;
    return ans;
}

int main() {
    //freopen("halfnice.in","r",stdin);
    int t;
    int x = N;
    for (int i = 2; i < x; i ++ ) {
        if (!v[i]) {
            prime[++tot] = i;v[i] = i;vv[i] = 1;
        }
        for (int j = 1; j <= tot; j ++ ) {
            if (prime[j] > v[i] || prime[j] > x / i ) break;
            v[i*prime[j]] = prime[j];
        }
    }
    int T = 1;
    cin >> t;
    while (t--) {
        ll l,r;
        scanf("%lld%lld",&l,&r);
        ll ans = l - 1;
        for (ll i = r; i >= l; i -- ) {
            int div = ceil((ff)num(i)*1.0/2);
            ll mm = MOD(div);
            ll x = i / mm, y = i % mm;
            if (vv[x]) {
                if (x > y) i = i - y - 1;
                else {
                    ans = max(ans, i - (y % x));
                    i = i - (y % x);
                    break;
                }
            }else { 
                if (__gcd(x,y) != 1 && y != 0) {
                    ans = max(ans,i);
                    break;
                }
            }
        }
        printf("Case %d: ",T++);
        if (ans != l - 1) printf("%lld\n",ans);
        else puts("impossible");
    }
    return 0;
}