首页 > 代码库 > 01——数论题解

01——数论题解

T1.最大质因子(bigfact)

        有n个数,求最大质因子最大的数。

              筛法+枚举

T2.奶牛的足球1(football1)

        给出n(<=10^15)转化成m进制,然后分别写出每位展开的权值。

              高精度的进制转换,打了好久的模板(累ing)(*,/,%,=,<等等)

 

T3.狐狸抓兔子(security)

        N个洞,不删数的约瑟夫,周期m,求不会找到的洞的总数并输出从大到小前10个。

              gcd(n,m)的倍数都是会被找到的,所以就是求gcd,然后判断是否倍数(输出10个)。

 

T4.奶牛的足球2(football2)

        两堆球,a,b个,每次从多的那堆取出另一堆个数的球放到另一堆中,求最少次数或-1

              用一下倒推的方法:

技术分享

可以发现,tot=t*2k,则必有a=t*x,b=t*y

              所以每次tot>>1,k<<1 然后判断

(a%tmp==0,b%tmp==0,a/sum+b/sum=tmp)

然后就可以判断了。如果某次(sum&1)就说明无解了。

01——数论题解