A - Divisibility Shortcut -Kattis - shortcut
发布日期:2022-02-10 08:11:10 浏览次数:9 分类:技术文章

本文共 1762 字,大约阅读时间需要 5 分钟。

**A - Divisibility Shortcut ***

There is a well-known shortcut (or “trick”) for determining whether or not a non-negative integer n is divisible by 3:
Add up the digits in the base-10
representation of n; call this sum S10(n)。
If S10(n)is divisible by 3, then n is divisible by 3
It turns out that this idea can be generalized to other bases and divisors. Let b≥2
and d≥1 be integers. For any integer n≥0, define Sb(n) to be the sum of the digits in the base-b representation of n. We say that DS(b,d) holds (DS stands for “divisibility shortcut”) if the following is true: for all integers n≥0, if Sb(n) is divisible by d, then n is divisible by d
Given integers b≥2
and k≥1, find the largest integer d≤k such that DS(b,d)
holds.
Input
The first line of input contains an integer T
(1≤T≤100), the number of test cases. This is followed by T lines, one per test case, each of which contains two space-separated integers, b and k (2≤b≤109, 1≤k≤109)
Output
For each test case, output a single line containing the largest integer d≤k
such that DS(b,d)
holds.
Sample Input 1
2
10 5
24 11
Sample Output 1
3
1
题意:求最大d<=k,满足对于任何数如果以b为基数的各个位数上的和能整除d,则可以得到该数一定能整除d
解题思路:x0b0+x1b1+…+xmbm=ds,x0+x1+…+xm=dk,s和k为任意整数,将两式相减,得到x1(b-1)+x2(bb-1)+…+xm(b^m-1)=d(s-k),易知左边各项含有一个公倍数为b-1,所以d肯定为b-1的一个因数且小于k,该题就变成了找b-1的因数

AC代码:#include
   
    #include
    
     #include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #define maxn 1359using namespace std;typedef long long ll;int main(){
            
int t;
cin>>t;
while(t--)
{
int b,k;
scanf("%d%d",&b,&k);
int pig=-1,ans=b-1,j=sqrt(ans+1);
for(int i=1;i<=j;i++)
{
if(ans%i==0)
{
if(ans/i>k&&i<=k)
pig=max(pig,i);
else if(ans/i<=k)
pig=max(pig,ans/i);
}
}
printf("%d\n",pig);
}
return 0;}

转载地址:https://blog.csdn.net/qq_44632981/article/details/98366311 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!

上一篇:Backward Digit Sums-POJ - 3187 -枚举-穷竭搜索
下一篇:Tour - UVA - 1347-动态规划

发表评论

最新留言

能坚持,总会有不一样的收获!
[***.13.112.176]2022年08月18日 05时37分52秒
第一次来,支持一个
[***.67.49.66]2022年08月18日 05时37分47秒

关于作者

    喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!

最新文章

ROS中tf学习笔记 2019-12-04 00:26:43
git相关指令 2019-12-04 00:26:43
粒子滤波学习记录 2019-12-04 00:26:43
机器人前行、旋转的service编写 2019-12-04 00:26:43
ROS 中 boost::bind( ) 的使用 2019-12-04 00:26:43
JavaScript基础 2019-12-04 00:26:40
JavaScript操作DOM对象 2019-12-04 00:26:41
初始jQuery 2019-12-04 00:26:41
JavaScript操作BOM对象 2019-12-04 00:26:41
模式识别期末考试名词解释总结 2019-12-04 00:26:41
C语言课后问答题汇总 2019-12-04 00:26:41
IMU的学习记录 2019-12-04 00:26:42
Kinect2.0+ORBSLAM2_with_pointcloud_map 2019-12-04 00:26:42
数据库的设计 2019-12-04 00:26:39
MySQL高级查询 2019-12-04 00:26:39
认识MySqL 2019-12-04 00:26:39
高级查询(二) 2019-12-04 00:26:40
事务·视图·索引·备份和恢复 2019-12-04 00:26:40
MySql存储过程 2019-12-04 00:26:40
DAO模式 2019-12-04 00:26:40