2011年省赛选拔之数论组合数学专题解题报告

D题.....-by sharon

D:C Looooops

题目数据范围很大,显然不能用模拟,但是可以用求不定方程来得出答案,关键是要用int64(long long)

模型:求 a+cx=b(mod 2^k) 最小正整数解 (0=<a,b,c<2^k,这个范围比较重要)
      我们通过扩展欧几里德求得一解 x,(无解就输出FOREVER)
      x%=(2^k/d),if(x<0) x+==(2^k/d).x为答案。

网上的讲法很多,有叫欧几里德扩展法,也有叫线性同余的,感觉思路都是一样的。关键就在判断是否有解(即是否为FOREVER)。

(第一次写解题报告。。。有水分。。)


为解题报告打分
暂时不评分

★★
★★★
★★★★
★★★★★
发表您的评论(若贴AC代码或发表禁止言论等违禁行为将被删除并扣除积分)

|返回 |   | 转到页头|
Copyright @ 2008-2024(浙ICP备2022001332号), TZOJ. All Rights Reserved.