近日数论心得

#牛客激励计划#
首先是一道gcd题目，洛谷P1029，不是很难，就是解法较为数学化
先上题目

题目描述
输入两个正整数 x0 ,y0求出满足下列条件的 P,Q 的个数：
P,Q 是正整数。
要求 P,Q 以 x0为最大公约数，以 y0为最小公倍数。

试求：满足条件的所有可能的 P,Q 的个数。

输入格式
一行两个正整数 x0,y0。

输出格式
一行一个数，表示求出满足条件的 P,Q 的个数。

输入
3 60
输出
4
说明/提示
P,Q 有 4 种：
3,60。
15,12。
12,15。
60,3。

我的思路
x=gcd(p,q)
y=lcm(p,q)
注意到，p*q=x*y
设p*q有因数x,x,n1,n2,n3....
则y/x的因数为n1,n2,n3....
相当于有2个1(看做p,q的初始基础值)，使它们都变为x（一个叫左x,一个叫右x）
若n1,n2,n3...中有相同的数（nx=ny），则视为同一个数(即不能分开放到左右x上)
那么在新的n1,n2,n3...中，
挑选0个，乘入左x,挑选1个，放入左x（剩下的就放到右x了）
这样继续下去，就是排列组合中的C了，所有C的和就是n²（n为n1,n2,n3...的个数）
即可得出答案，别忘了，y不一定是x的倍数，要加个特判

Python代码如下
a,b=map(int,input().split())
f=0
if b%a!=0:
    f=1
b=b//a
s=0
if f==0:
    for i in range(2,b+1):
        f=0
        while b%i==0:
            b=b//i
            if f==0:
                s+=1
            f=1
    print(2 ** s)
else:
    print(0)

还有一道是新鲜出炉的dfs+素数组合，洛谷P1036
题目如下
题目描述
已知 n 个整数 x1,x2 ,⋯,xn，以及 1 个整数 k（k<n）。从 n 个整数中任选 k 个整数相加，可分别得到一系列的和。例如当 n=4，k=3，4 个整数分别为 3,7,12,19 时，可得全部的组合与它们的和为：
3+7+12=22
3+7+19=29
7+12+19=38
3+12+19=34
现在，要求你计算出和为素数共有多少种。
例如上例，只有一种的和为素数：3+7+19=29。

输入格式
第一行两个空格隔开的整数 n,k（1≤n≤20，k<n）。
第二行 n 个整数，分别为 x1,x2 ,⋯,xn（1≤x i≤5×10 6）。

输出格式
输出一个整数，表示种类数。

输入输出样例
输入
4 3
3 7 12 19
输出
1

将输入的第二行记为列表l
首先素数判断不是难点，就不讲了
基础的dfs解决不了此问题，因为可能会重复
那么要怎么做到不重不漏呢？
定义了一个列表f，用于标记某指针的范围

例如第一层dfs （以下记为dfs(1)）
那么此dfs(1)的指针（以下记为d1）范围应为整个l，起始时指向l[0]
dfs(2)的指针d2的范围应为l[1:n]
那么不妨设k=2,当d2遍历一遍l到d2指向l[n-1]时，
d1就应指向l[1],d2范围为l[2:n]

那么如果有d3,d4...呢？
dx的范围就是d(x-1)指向的位置+1到l的末尾
那么每次dx更新指向为y，就应将f[x:n]更新为y
保证后面的指针不会跨越前面的指针，就做到了不重，至于不漏，那就是dfs本身了

Python代码如下

def ispr(n):
    if n==2 or n==3:
        return 1
    elif n<=1:
        return 0
    for i in range(2,int(n**(1/2))+1):
        if n%i==0:
            return 0
    return 1

def dfs(k1,k2,n):
    if k1==k2:
        a=0
        for i in range(n):
            if l2[i]==1:
                a+=l1[i]
        s.append(a)
        return 0
    for i in range(f[k1],n):
        for j in range(k1,k2):
            f[j]=i

        if l2[i]==0:
            l2[i]=1
            dfs(k1+1,k2,n)
            l2[i]=0

n,k=map(int,input().split())
l1=list(map(int,input().split()))
l2=[0]*n
s=[]
f=[0]*k
dfs(0,k,n)
ans=0
for i in s:
    if ispr(i):
        ans+=1
print(ans)

不经常写题解，而且我的算法水平并不高，若是有不当的地方，请指正