[NOIP2000 提高组] 进制转换

题目描述

我们可以用这样的方式来表示一个十进制数: 将每个阿拉伯数字乘以一个以该数字所处位置为指数,以 $10$ 为底数的幂之和的形式。例如 $123$ 可表示为 1×102+2×101+3×1001 \\times 10^2+2\\times 10^1+3\\times 10^01×102+2×101+3×100 这样的形式。

与之相似的，对二进制数来说，也可表示成每个二进制数码乘以一个以该数字所处位置为指数,以 $2$ 为底数的幂之和的形式。

一般说来，任何一个正整数 $R$ 或一个负整数 $-R$ 都可以被选来作为一个数制系统的基数。如果是以 $R$ 或 $-R$ 为基数,则需要用到的数码为 $0,1,....R-1$。

例如当 $R=7$ 时,所需用到的数码是 $0,1,2,3,4,5,6$，这与其是 $R$ 或 $-R$ 无关。如果作为基数的数绝对值超过 $10$,则为了表示这些数码，通常使用英文字母来表示那些大于 $9$ 的数码。例如对 $16$ 进制数来说,用 $A$ 表示 $10$,用 $B$ 表示 $11$，用 $C$ 表示 $12$，以此类推。

在负进制数中是用 $-R $ 作为基数，例如 $-15$（十进制）相当于 (110001)−2(110001)_{-2}(110001)−2​ （$-2$进制），并且它可以被表示为 $2$ 的幂级数的和数：

(110001)−2=1×(−2)5+1×(−2)4+0×(−2)3+0×(−2)2+0×(−2)1+1×(−2)0(110001)_{-2}=1\\times (-2)^5+1\\times (-2)^4+0\\times (-2)^3+0\\times (-2)^2+0\\times (-2)^1 +1\\times (-2)^0(110001)−2​=1×(−2)5+1×(−2)4+0×(−2)3+0×(−2)2+0×(−2)1+1×(−2)0

设计一个程序,读入一个十进制数和一个负进制数的基数, 并将此十进制数转换为此负进制下的数。

输入格式

输入的每行有两个输入数据。

第一个是十进制数 $n$。
第二个是负进制数的基数 $-R$。

输出格式

输出此负进制数及其基数，若此基数超过 $10$，则参照 $16$ 进制的方式处理。

样例 #1

样例输入 #1

30000 -2

样例输出 #1

30000=11011010101110000(base-2)

样例 #2

样例输入 #2

-20000 -2

样例输出 #2

-20000=1111011000100000(base-2)

样例 #3

样例输入 #3

28800 -16

样例输出 #3

28800=19180(base-16)

样例 #4

样例输入 #4

-25000 -16

样例输出 #4

-25000=7FB8(base-16)

提示

【数据范围】
对于 $100\%$ 的数据，$-20\le R\le -2$，$|n|\le 37336$。

NOIp2000提高组第一题

思路

首先我们要清楚十进制到底怎么转变为其他进制的。假设十进制数15转换为2进制。$15=((1\times 2+1)\times 2+1)\times 2+1$，只需要不断取模，整除。循环下去，直到整除为0时，模数排列即1111。本质上得到的每个位的位数都代表了这个数的进制权数，也就是乘上(位数-1)个2.
对于负进制数假设为$-2$进制则可表示为$15=(((1\times -2)\times -2)\times -2)\times -2-1$,按照原来方法，模数有负数。需要将其变形一下根据$被除数=商\times 除数+余数\equiv (商+1)\times 除数+余数-除数$，$15=(((1\times -2)\times -2)\times -2+1)\times -2+1$，得到的-2进制数为10011.则在变换时，碰到负的余数，将其所得的$余数-除数$，$商+1$即可。

代码

def convert(n, base) :res = ''if n == 0 :return 0while n :t = n % basen //= baseif t < 0 :n += 1t -= baseif t >= 10 :t = chr(ord('A') + t - 10)res = str(t) + resreturn res
n, base = map(int, input().split())
res = convert(n, base)
print(f"{n}={res}(base{base})")

直线交点数

题目描述

假设平面上有 $N$ 条直线，且无三线共点，那么这些直线一共能有多少不同的交点数？

输入格式

一行，一个整数 $N$，代表有 $N$ 条直线。

输出格式

一行，一个整数，表示方案总数。

样例 #1

样例输入 #1

4

样例输出 #1

5

提示

对于所有数据，满足 $1\le N\le 25$。

思路

对于一堆(N)直线，可以将其分为两堆，一堆§是相互平行的直线，一堆(N -r)是与另一堆不平行的直线。这两堆直线间的交点是$p\times (N-r)$。平行直线间没有交点，与另一堆不平行的直线也可以按照此方法计算交点，直到平行直线为0，没有交点。
递归思路，假设当前有n调直线，枚举平行直线数量，记录两堆直线间的交点，继续递归处理不平行的那一堆直线，直到剩余直线为0.

代码

N = 25 * 25 + 10
st = [False] * N
ans = 0
def dfs(n, s) : # 分别表示当前处理的直线堆、已算出的交点数global ansif n == 0 : # 终止条件if not st[s] :ans += 1st[s] = Truereturn# 枚举平行线数for i in range(1, n + 1) :dfs(n - i, s + i * (n - i))
n = int(input())
dfs(n, 0)
print(ans)

编码

题目描述

编码工作常被运用于密文或压缩传输。这里我们用一种最简单的编码方式进行编码：把一些有规律的单词编成数字。

字母表中共有26个字母{a，b，…，z}，这些特殊的单词长度不超过6且字母按升序排列。把所有这样的单词放在一起，按字典顺序排列，一个单词的编码就对应着它在字典中的位置。

例如：

a→1 b→2 z→26 ab→27 ac→28

你的任务就是对于所给的单词，求出它的编码。

输入格式

仅一行，被编码的单词。

输出格式

仅一行，对应的编码。如果单词不在字母表中，输出0。

样例 #1

样例输入 #1

ab

样例输出 #1

27

思路

以cgx为例

1. 首先长度为1的单词一定小于它C261C_{26}^1C261​
2. 长度为2的单词一定小于它C262C_{26}^2C262​
3. 第一个字母小于c的情况一定小于它C242C_{24}^2C242​
4. 第一个字母等于c的情况，且小于gx的单词一定小于它（递归处理即可）。

代码

又是毕业季II

题目背景

“叮铃铃铃”，随着高考最后一科结考铃声的敲响，三年青春时光顿时凝固于此刻。毕业的欣喜怎敌那离别的不舍，憧憬着未来仍毋忘逝去的歌。一千多个日夜的欢笑和泪水，全凝聚在毕业晚会上，相信，这一定是一生最难忘的时刻！

题目描述

彩排了一次，老师不太满意。当然啦，取每位同学的号数来找最大公约数显然不太合理。于是老师给每位同学评了一个能力值。于是现在问题变为，从 $n$ 个学生中挑出 $k$ 个人使得他们的默契程度（即能力值的最大公约数）最大。但因为节目太多了，而且每个节目需要的人数又不知道。老师想要知道所有情况下能达到的最大默契程度是多少。这下子更麻烦了，还是交给你吧~

PS：一个数的最大公约数即本身。

输入格式

第一行一个正整数 $n$。

第二行为 $n$ 个空格隔开的正整数，表示每个学生的能力值。

输出格式

总共 $n$ 行，第 $i$ 行为 $k=i$ 情况下的最大默契程度。

样例 #1

样例输入 #1

4
1 2 3 4

样例输出 #1

4
2
1
1

提示

【题目来源】

lzn 原创

【数据范围】

记输入数据中能力值的最大值为 $\text{inf}$。

• 对于 $20\%$ 的数据，$n\le 5$，inf≤103\\textit{inf}\\leq 10^3inf≤103；
• 对于另 $30\%$ 的数据，$n\le 100$，$\text{inf}\le 10$；
• 对于 $100\%$ 的数据，n≤104n \\leq 10^4n≤104，inf≤106\\textit{inf} \\leq 10^6inf≤106。

思路

求解1-n个数中$1-n$个数的最大公因子。一个暴力的思路就是就这1~n的组合数，然后求最大公因子可以过30%的数据。
要想ac，得从因子本身出发，假设求k个数的最大公因子，那么对于这个因子而言一定被大于等于k个数所共有，那么我们可以通过统计所有数的因子数情况，比较因子数大于等于k的最大因子，就是k个数的最大公因子。

代码

N = 1000010C = [0] * N
A = [0] * N
t = 0def get_factor(num) : # 求约数(O(sqrt(n)))i = 1while i <= num // i :if num % i == 0 :C[i] += 1if i != num // i :C[num // i] += 1i += 1n = int(input())
A[1 : n + 1] = list(map(int, input().split()))
# 记录所有数因子情况
for i in range(1, n + 1) :t = max(t, A[i])get_facotor(A[i])for i in range(1, n + 1) : # 因子数也具有单调性if C[t] < i : t-= 1print(t)

签到题

题目背景

这是一道签到题！

建议做题之前仔细阅读数据范围！

题目描述

我们定义一个函数：$\mathrm{qiandao}(x)$ 为小于等于 $x$ 的数中，与 $x$ 不互质的数的个数。

这题作为签到题，给出 $l$ 和 $r$，求出：

∑i=lrqiandao⁡(i)mod666623333\\sum_{i=l}^r \\operatorname{qiandao}(i)\\bmod 666623333i=l∑r​qiandao(i)mod666623333

输入格式

一行两个整数，$l$、$r$。

输出格式

一行一个整数表示答案。

样例 #1

样例输入 #1

233 2333

样例输出 #1

1056499

样例 #2

样例输入 #2

2333333333 2333666666

样例输出 #2

153096296

提示

• 对于 $30\%$ 的数据，l,r≤103l,r\\leq 10^3l,r≤103。
• 对于 $60\%$ 的数据，l,r≤107l,r\\leq 10^7l,r≤107。
• 对于 $100\%$ 的数据，1≤l≤r≤10121 \\leq l \\leq r \\leq 10^{12}1≤l≤r≤1012，r−l≤106r-l \\leq 10^6r−l≤106。

(30点)

'''
筛法筛欧拉函数，用筛好的欧拉函数，继续筛区间欧拉函数
'''
from math import ceil
N = 1000010
MOD = 666623333eula = [0] * N
st = [False] * N
primes = []def init(n) :for i in range(2, n + 1) :if not st[i] :primes.append(i)for j in primes :if i * j > n : breakst[i * j] = Trueif i % j == 0 :breakinit(N - 1)
l, r = map(int, input().split())def get_eula(x) :res = xfor i in primes :if i > x : breakflag = Truewhile x % i == 0 :x //= iflag = Falseif not flag :res = res * (i - 1) // ireturn res# 区间筛质数
st = [False] * N
for i in primes[:-1] :if i > r : breakj = max(2, ceil(l / i)) * iwhile j <= r :st[j - l] = Truej += ifor i in range(l, r + 1) :if i >= 2 and not st[i - l] :eula[i - l] = i - 1elif i < 2 : eula[i] = 1else :eula[i - l] = get_eula(i)
res = 0
for i in range(l, r + 1) :res = (res + i - eula[i - l]) % MOD
print(res)