杭电多校第六场 1009 Divisibility 题解

题目大意

给你两个数,b和x,问在b进制下,将任意一个数y的每一位不断加起来,直到只有一位,问是否满足这一位数能被x整除,则y被x整除,否则则不能整除的理论。

解题思路

其实这个也不算难证,比赛的时候脑抽了,卡了好久。。

证明就懒得证了,直接上官方题解吧。

(证的又详细还比我好。。

由这个定理可知,$f(a)=f(a\ mod\ m)$。

所以只要$\displaystyle f(y) = \sum_{i=1}^n c_i\equiv 0 \pmod{x}$则$\underbrace{f( f( \cdots f(y) \cdots ))}_{\infty} \equiv 0 \pmod{x}$

那么原命题等价于:对于任意的 $b$ 进制正整数 $y = \overline{c_1 c_2 \cdots c_n}$,如果 $c_1 + c_2 + \cdots + c_n \equiv 0 \pmod{x}$,那么 $y \equiv 0 \pmod{x}$,否则 $y \not\equiv 0 \pmod{x}$。

上述命题成立当且仅当 $b \equiv 1 \pmod{x}$。

证明:

  • 当 $b \equiv 1 \pmod{x}$ 时,有 $y \equiv c_1 b^{n-1} + c_2 b^{n-2} + \cdots + c_n b^0 \equiv c_1 + c_2 + \cdots + c_n \pmod{x}$,于是上述命题成立。
  • 当 $b \not\equiv 1 \pmod{x}$ 时,假设上述命题成立,有:
    • 若 $x \leq b$,令 $y = 1 \cdot b^1 + (x-1) b^0$,则应有 $y \equiv b + x - 1 \equiv 0 \pmod{x}$,即 $b \equiv 1 \pmod{x}$,但此时 $b \not\equiv 1 \pmod{x}$,出现矛盾,于是上述命题不成立。
    • 若 $x > b$,令 $y = x = \overline{c_1 c_2 \cdots c_n}$,显然 $c_1 + c_2 + \cdots + c_n \not\equiv 0 \pmod{x}$,于是 $y \not\equiv 0 \pmod{x}$,但 $y \equiv 0 \pmod{x}$,出现矛盾,于是上述命题不成立。

综上,上述命题成立当且仅当 $b \equiv 1 \pmod{x}$。

完整代码

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
#include <bits/stdc++.h>
#include <iostream>
#include <cstdio>
#include <queue>
#include <cstring>
#include <cmath>
#include <stack>
#include <map>
#include <string>
#include <vector>
#include <algorithm>
#include <sstream>
#include <unordered_map>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;

const ll mod = 998244353;

ll slove(ll a) {
if (a < 10) return a;
ll ans = 0;
while (a) {
ans += a % 10, a /= 10;
}
slove(ans);
}

int main() {
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
int t;
cin >> t;
while (t--) {
ll n;
ll x;
cin >> n >> x;
if ((n-1)%x==0) cout << "T" << endl;
else cout << "F" << endl;
}
return 0;
}
  • 版权声明: 本博客所有文章除特别声明外,著作权归作者所有。转载请注明出处!
  • © 2015-2021 sakurakarma
  • Powered by Hexo Theme Ayer
  • PV: UV:

请我喝杯咖啡吧~

支付宝
微信