「51Nod1132」覆盖数字的数量V2&「Ural1797」 Summit Online Judge.Version 2-类欧几里得

发布于 4 天前  17 次阅读


本文章由SYCstudio或本站其它作者所有,请勿擅自转载

本文链接地址:「51Nod1132」覆盖数字的数量V2&「Ural1797」 Summit Online Judge.Version 2-类欧几里得

Description

链接

Solution

只需求$[0,n]$的答案然后相减即可。

考虑$gcd(a,b)=1$的情况(如果$gcd(a,b)>1$那么$a,b,n$同除以$gcd(a,b)$即可)

对于一组询问$(a,b,n)$如果$n>(a-1)(b-1)$,那么$>(a-1)(b-1)$的部分肯定可以凑出来(小凯的疑惑)。

$\leq (a-1)(b-1)$的部分最多只有一组非负整数解,用类欧几里得统计$ax+by\leq n$的方案数即可(同BZOJ2987)。

本文章由SYCstudio或本站其它作者所有,请勿擅自转载

本文链接地址:「51Nod1132」覆盖数字的数量V2&「Ural1797」 Summit Online Judge.Version 2-类欧几里得


或许前方只有...伸手不见五指的夜路,即使如此,我还是要充满信心、继续向前, 相信星星的光芒...多少会照亮前方的道路,走吧!我们踏上旅程吧!