【数论】有关模运算的巧妙

萌萌的好数

链接：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 ≤ 10¹²

输出描述:

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

示例1

输入

输出

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 个好数

#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 的情况的讨论
这样计算后，将其第一个第二个加起来，减去第三个就是不是好数的个数，也就能统计出好数的个数

#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 - 1if(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;
}

或者

#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, 能构成的好数的集合

#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，已经 returnif(!limit) dp[weishu][sum] = ans;// 这里就是 limit == 1 的时候单独讨论，返回，怕影响 dpreturn 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;
}