洛谷——数学1(好题与错题)

时间:2021-01-04 01:11:30

[NOIP2000 提高组] 进制转换

题目描述

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

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

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

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

在负进制数中是用 $-R $ 作为基数,例如 − 15 -15 15(十进制)相当于 ( 110001 ) − 2 (110001)_{-2} (110001)2 − 2 -2 2进制),并且它可以被表示为 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 n n
第二个是负进制数的基数 − R -R R

输出格式

输出此负进制数及其基数,若此基数超过 10 10 10,则参照 16 16 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 % 100\% 100% 的数据, − 20 ≤ R ≤ − 2 -20 \le R \le -2 20R2 ∣ n ∣ ≤ 37336 |n| \le 37336 n37336

NOIp2000提高组第一题

思路

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

代码

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

直线交点数

题目描述

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

输入格式

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

输出格式

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

样例 #1

样例输入 #1

4

样例输出 #1

5

提示

对于所有数据,满足 1 ≤ N ≤ 25 1 \le N \le 25 1N25

思路

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

代码

N = 25 * 25 + 10
st = [False] * N
ans = 0
def dfs(n, s) : # 分别表示当前处理的直线堆、已算出的交点数
	global ans
	if n == 0 : # 终止条件
		if not st[s] :
			ans += 1
			st[s] = True
		return
	# 枚举平行线数
	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的单词一定小于它 C 26 1 C_{26}^1 C261
  2. 长度为2的单词一定小于它 C 26 2 C_{26}^2 C262
  3. 第一个字母小于c的情况一定小于它 C 24 2 C_{24}^2 C242
  4. 第一个字母等于c的情况,且小于gx的单词一定小于它(递归处理即可)。

代码


又是毕业季II

题目背景

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

题目描述

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

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

输入格式

第一行一个正整数 n n n

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

输出格式

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

样例 #1

样例输入 #1

4
1 2 3 4

样例输出 #1

4
2
1
1

提示

【题目来源】

lzn 原创

【数据范围】

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

  • 对于 20 % 20\% 20% 的数据, n ≤ 5 n \leq 5 n5 inf ≤ 1 0 3 \textit{inf}\leq 10^3 inf103
  • 对于另 30 % 30\% 30% 的数据, n ≤ 100 n \leq 100 n100 inf ≤ 10 \textit{inf} \leq 10 inf10
  • 对于 100 % 100\% 100% 的数据, n ≤ 1 0 4 n \leq 10^4 n104 inf ≤ 1 0 6 \textit{inf} \leq 10^6 inf106

思路

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

代码

N = 1000010

C = [0] * N
A = [0] * N
t = 0

def get_factor(num) : # 求约数(O(sqrt(n)))
	i = 1
	while i <= num // i :
		if num % i == 0 :
			C[i] += 1
			if i != num // i :
				C[num // i] += 1
		i += 1

n = 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-= 1
	print(t)

签到题

题目背景

这是一道签到题!

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

题目描述

我们定义一个函数: qiandao ⁡ ( x ) \operatorname{qiandao}(x) qiandao(x) 为小于等于 x x x 的数中,与 x x x 不互质的数的个数。

这题作为签到题,给出 l l l r r r,求出:

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

输入格式

一行两个整数, l l l r r r

输出格式

一行一个整数表示答案。

样例 #1

样例输入 #1

233 2333

样例输出 #1

1056499

样例 #2

样例输入 #2

2333333333 2333666666

样例输出 #2

153096296

提示

  • 对于 30 % 30\% 30% 的数据, l , r ≤ 1 0 3 l,r\leq 10^3 l,r103
  • 对于 60 % 60\% 60% 的数据, l , r ≤ 1 0 7 l,r\leq 10^7 l,r107
  • 对于 100 % 100\% 100% 的数据, 1 ≤ l ≤ r ≤ 1 0 12 1 \leq l \leq r \leq 10^{12} 1lr1012 r − l ≤ 1 0 6 r-l \leq 10^6 rl106

(30点)

'''
筛法筛欧拉函数,用筛好的欧拉函数,继续筛区间欧拉函数
'''
from math import ceil
N = 1000010
MOD = 666623333

eula = [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 : break
            st[i * j] = True
            if i % j == 0 :
                break

init(N - 1)
l, r = map(int, input().split())

def get_eula(x) :
    res = x
    for i in primes :
        if i > x : break
        flag = True
        while x % i == 0 :
            x //= i
            flag = False
        if not flag :
            res = res * (i - 1) // i
    return res

# 区间筛质数
st = [False] * N
for i in primes[:-1] :
    if i > r : break
    j = max(2, ceil(l / i)) * i
    while j <= r :
        st[j - l] = True
        j += i

for i in range(l, r + 1) :
    if i >= 2 and not st[i - l] :
        eula[i - l] = i - 1
    elif i < 2 : eula[i] = 1
    else :
        eula[i - l] = get_eula(i)
res = 0
for i in range(l, r + 1) :
    res = (res + i - eula[i - l]) % MOD
print(res)