首页 > 代码库 > URAL 1355. Bald Spot Revisited（数论）
URAL 1355. Bald Spot Revisited（数论）
题目链接
题意 ： 一个学生梦到自己在一条有很多酒吧的街上散步。他可以在每个酒吧喝一杯酒。所有的酒吧有一个正整数编号，这个人可以从n号酒吧走到编号能整除n的酒吧。现在他要从a号酒吧走到b号，请问最多能喝到多少酒。
思路 ：因为b肯定要是a的倍数，是a从头开始乘下去的，实际上就是找构成b/a的素数划分，有多少个素数划分就可以喝到多少的酒。
1 #include <stdio.h> 2 #include <string.h> 3 #include <iostream> 4 5 using namespace std ; 6 7 int sumnum(int n) 8 { 9 for(int i = 2 ; i * i <= n ; i++)//素数10 {11 if(n % i == 0){//为0就说明多了一个，然后剩下的数接着找12 return 1 + sumnum(n / i) ;13 }14 }15 return 0 ;16 }17 int main()18 {19 int T ;20 scanf("%d",&T) ;21 int a,b ;22 while(T--)23 {24 scanf("%d %d",&a,&b) ;25 if(b % a != 0)26 {27 printf("0\n") ;28 continue ;29 }30 else if(a == b)31 {32 printf("1\n") ;33 continue ;34 }35 int ans = sumnum(b / a);36 printf("%d\n",ans+2) ;//加上a和b37 }38 return 0 ;39 }
URAL 1355. Bald Spot Revisited（数论）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。