算法-对于数列an = c1*n+c2, c1和c2为正整数，如何判断an中是否存在3的倍数？

Question

如果存在的话，能否求出an中所有小于给定的数N的3的倍数？

Answer 1

设c1=3w+x, c2=3y+z, 其中w、y为任意非负整数，x、z为0、1或2
那么：an = c1 * n + c2 = 3nw + nx + 3y + z
问an能否被3整除，等同于问f(n)=nx+z能否被3整除

1 当z=0(即c2能被3整除)时：只要n取任意3的倍数，结果都能被3整除（当c1也能被0整除是，n可以取任意的整数)
2 z!=0且x=0(即c1能被3整除，c2不能)时,f(n)恒等于z，不可能被3整除
3 z!=0且x!=0(c1、c2都不能被3整除)时，
3.1 当x=z时： (nx + z) mod 3 = (n+1)x mod 3，只要n取3的倍数减1即可保证被3整除
3.2 当x!=z，可得x+z=3,那
(nx+z) mod 3 = (nx + 3 - x) mod 3 = ((n-1)x + 3) mod 3
,只要n取3的倍数加1即可保证被3整除

-------------------------我是华丽的分割线--------------------------
综合上述内容，只要c1不能被3整除，或者c2能被3整除时，an都存在3的倍数

至于“如果存在的话，能否求出an中所有小于给定的数N的3的倍数”，可以根据上述推论中n的取值方式，自己推算或者写程序输出，这里就不写了