不要你离开

相关推荐

首先是一道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)不经常写题解,而且我的算法水平并不高,若是有不当的地方,请指正
点赞 评论 收藏
分享
牛客网
牛客企业服务