数论--有关模运算的巧妙

萌萌的好数

链接：https://ac.nowcoder.com/acm/contest/84851/D
来源：牛客网

时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 262144K，其他语言524288K
64bit IO Format: %lld

题目描述

萌萌喜欢“好数”，这种“好数“需要满足以下两个条件：
1.该数对 3 取模不为 0
2.该数的最后一位数字不为 3
请你告诉他第 n 个好数是什么。

输入描述:

第一行读入一个正整数 t，表示有 t 组数据。
接下来 t 行，每行一个正整数 n。
1 ≤ t ≤ 100 1 ≤ n ≤ 1012

输出描述:

对于每个 n，输出一个正整数，为第 n 个好数

示例1

输入

1
2
3
4
3
1
4
9

输出

1
2
3
1
5
14

说明

前 9 个好数为 1，2，4，5，7，8，10，11，14。

解

方法一

  • 模 3 为 0 ，即每 3 个数一定为一个数，规律为 3
  • 最后一位为 3 ，即每 10 个数为一个周期
  • 这些要排除掉
  • 猜想规律为 30 一个周期，有规律出现，因为 3 和 10 的最小公倍数为 30，所以猜想 30 个数内可能有规律
  • 最后发现确实是，30 个数内都为 18 个好数
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include <iostream>
using namespace std;
typedef long long LL;
const int N = 30;
LL a[N] = { 1, 2, 4, 5, 7, 8, 10, 11, 14, 16, 17, 19, 20, 22, 25, 26, 28, 29 };

int main()
{
    int t;
    cin >> t;

    while (t--)
    {
        LL n;
        cin >> n;
        cout << ((n - 1) / 18) * 30 + a[((n - 1) % 18)] << endl;
    }
    return 0;
}

方法二

  • 用容斥原理的思想思考，将不是好数的排除掉，也就是假设一个当前数字，是否能算出包括它的前面所有数字中好数的个数
  • 这样在进行二分找数字，即可求解
  • 不是好数的满足
    • 能被 3 整除的数，有 n / 3 个，
    • 个位上是数字 3 的数个数，n / 10 + (n % 10 >= 3)
    • 个位上数字是 3 并且又能被 3 整除，n / 3 / 10 + ((n / 3) % 10 >= 1)，n / 3 是所有的能被 3 整除的数，在除以 10 就是个位是 3 的周期，最后的处理是除以 10 为 0 的情况的讨论
  • 这样计算后，将其第一个第二个加起来，减去第三个就是不是好数的个数，也就能统计出好数的个数
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
#include <iostream>
#include <vector>
using namespace std;
typedef long long LL;
LL n;

bool check(LL x)
{
    LL sum1 = x / 3;
    LL sum2 = x / 10 + (x % 10 >= 3);
    LL sum3 = (x/3) / 10 + ((x/3) % 10 >= 1);
    LL sum = x - (sum1 + sum2 - sum3);
    // 注意这里不能反正写判断，因为会找到比实际数大的情况出现，比如样例
    // 5 是答案，反着找到的 6 也满足，因为 6 不是好数，所以等同于 5 ，但是会找到 6 ，这就有问题，
    // 反着是指：if(sum <= n) return true; 然后二分边界也随之改变为l = mid,r = mid - 1
    if(n <= sum) return true;    
    else return false;
}

int main()
{
    int T;
    cin >> T;
    while(T--)
    {
        cin >> n;
    
        LL l = 1, r = 1e14;
        while(l < r)
        {
            LL mid = l + r >> 1;
            if(check(mid)) r = mid;
            else l = mid + 1;
        }
        cout << r << endl;
    }
    return 0;
}

或者

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
#include <iostream>
#include <vector>
using namespace std;
typedef long long LL;
LL n;

bool check(LL x)
{
    LL sum1 = x / 3;
    LL sum2 = x / 10 + (x % 10 >= 3);
    LL sum3 = (x/3) / 10 + ((x/3) % 10 >= 1);
    LL sum = x - (sum1 + sum2 - sum3);
    if(sum < n) return true;
    else return false;
}

int main()
{
    int T;
    cin >> T;
    while(T--)
    {
        cin >> n;
    
        LL l = 1, r = 1e14;
        while(l < r)
        {
            LL mid = l + r >> 1;
            if(check(mid)) l = mid + 1;
            else r = mid;
        }
        cout << r << endl;
    }
    return 0;
}

方法三

  • 记忆化搜索方式—-dp 方式
  • dp[i][j] 定义为第 i 位和为 j 的方案数
  • 从最高位开始 dfs 搜索，用 limit 作为限制，也就是后面的位的数字是否可以随便选择从 0~9 的任意数字
  • 如果 limit 为 0 ，表示没有限制，况且 dp 有值，那么直接返回即可，这里理解是都在没有限制的情况下，那么后面组成的情况都一致，就是加上当前位以前的 sum，满足好数的个数都一致，因为后面都没有限制，都是随便选择
  • 如果有限制，那么不返回，单独进行返回 ans，也就是计算的值
  • dp 记录的是这个位之后的数字加上当前位之前的 sum, 能构成的好数的集合
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
#include <iostream>
#include <cstring>
using namespace std;
typedef long long LL;
LL dp[20][200], num[20];
LL n;

// 位数 和 限制--最高位的取法
LL dfs(int weishu, int sum, int limit)
{
    if(weishu < 1)
    {
        if(sum % 3 == 0) return 0;
        else return 1;
    }
    
    if(!limit && dp[weishu][sum] != -1) return dp[weishu][sum];
    
    // 没有限制，就是 0~9，有限制就是当前位的最大数
    int maxnum = limit ? num[weishu] : 9;
    
    LL ans = 0;
    for(int i = 0; i <= maxnum; i++)
    {
        if(weishu == 1 && i == 3) continue;
        ans += dfs(weishu - 1, sum + i, (limit && i == maxnum));
    }
     // 这里不会重复更新，有数且满足 limit == 0，已经 return
    if(!limit) dp[weishu][sum] = ans;
     
     // 这里就是 limit == 1 的时候单独讨论，返回，怕影响 dp
    return ans;
}

bool check(LL x)
{
    memset(num, 0, sizeof num);
    memset(dp, -1, sizeof dp);
    
    int k = 0;
    while(x)
    {
        num[++k] = x % 10;
        x /= 10;
    }
    
    LL sum = dfs(k, 0, 1);
    if(sum < n) return true;
    else return false;
}

int main()
{
    int t;
    cin >> t;
    while(t--)
    {
        cin >> n;
        
        LL l = 0, r = 1e14;
        while(l < r)
        {
            LL mid = l + r >> 1;
            if(check(mid)) l = mid + 1;
            else r = mid;
        }
        cout << l << endl;
    }
    return 0;
}