首先是一道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=0if b%a!=0: f=1b=b//as=0if 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=223+7+19=297+12+19=383+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 33 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 1def 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]=0n,k=map(int,input().split())l1=list(map(int,input().split()))l2=[0]*ns=[]f=[0]*kdfs(0,k,n)ans=0for i in s: if ispr(i): ans+=1print(ans)不经常写题解，而且我的算法水平并不高，若是有不当的地方，请指正
投递京东等公司9个岗位