十四届蓝桥杯软件赛省赛Java大学A组互质数的个数

Question

十四届蓝桥杯软件赛省赛Java大学A组E题:互质数的个数,在求小于a的且与a互质的数的个数函数中为什么要定义一个times变量,且在times!=0时有res=resi%MOD;我的想法是只要a%i=0,即a可以整除i那么由欧拉函数的性质可得res=res(i-1);

Answer 1

在求小于a的且与a互质的数的个数函数中，定义一个times变量是为了统计与a不互质的数的个数，从而得到与a互质的数的个数。当times不为0时，表示存在与a不互质的数，需要将这部分数剔除掉，所以需要进行res *= i % MOD 的操作。

代码示例：

public class Main {private static final int MOD = 1000000007;
 
    public static void main(String[] args) {int a = 10;
int result = countCoPrimeNumbers(a);
System.out.println(result);
} 
    public static int countCoPrimeNumbers(int a) {int res = a;
int times = 1;
for (int i = 2;
 i <
 a;
 i++) {times = 1;
if (a % i == 0) {res = res * (i - 1) % MOD;
times = 0;
}}if (times != 0) {res = res * i % MOD;
}return res;
}}

有问题你别着急，评论留言都可以，看到马上就回复，尽量及时补充齐