文章目录
[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,....R−1。
例如当 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
−20≤R≤−2，
∣
n
∣
≤
37336
|n| \le 37336
∣n∣≤37336。
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)×−2−1,按照原来方法，模数有负数。需要将其变形一下根据
被除数
=
商
×
除数
+
余数
≡
(
商
+
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 1≤N≤25。
思路
对于一堆(N)直线，可以将其分为两堆，一堆§是相互平行的直线，一堆(N -r)是与另一堆不平行的直线。这两堆直线间的交点是
p
×
(
N
−
r
)
p \times (N - r)
p×(N−r)。平行直线间没有交点，与另一堆不平行的直线也可以按照此方法计算交点，直到平行直线为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的单词一定小于它 C 26 1 C_{26}^1 C261
- 长度为2的单词一定小于它 C 26 2 C_{26}^2 C262
- 第一个字母小于
c的情况一定小于它 C 24 2 C_{24}^2 C242 - 第一个字母等于
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 n≤5， inf ≤ 1 0 3 \textit{inf}\leq 10^3 inf≤103；
- 对于另 30 % 30\% 30% 的数据， n ≤ 100 n \leq 100 n≤100， inf ≤ 10 \textit{inf} \leq 10 inf≤10；
- 对于 100 % 100\% 100% 的数据， n ≤ 1 0 4 n \leq 10^4 n≤104， inf ≤ 1 0 6 \textit{inf} \leq 10^6 inf≤106。
思路
求解1-n个数中
1
−
n
1-n
1−n个数的最大公因子。一个暴力的思路就是就这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=l∑rqiandao(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,r≤103。
- 对于 60 % 60\% 60% 的数据， l , r ≤ 1 0 7 l,r\leq 10^7 l,r≤107。
- 对于 100 % 100\% 100% 的数据， 1 ≤ l ≤ r ≤ 1 0 12 1 \leq l \leq r \leq 10^{12} 1≤l≤r≤1012， r − l ≤ 1 0 6 r-l \leq 10^6 r−l≤106。
(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)