忽明忽暗

忽明忽暗

思路

先对100个灯输出结果来查看有没有规律：

//分析
public class Main{public static void main(String[] args){int n = 225;int[] s = new int[1000];for(int i=1; i<=n; i++){for(int j=1; j<=n; j++){if(j % i == 0)s[j] = s[j] ^ 1;}}//输出剩下开着灯的编号for(int i=1; i<=n; i++){if(s[i] == 1)System.out.print(i+" ");}}
}

输出结果：
1 4 9 16 25 36 49 64 81 100 121 144 169 196 225

规律：前n项平方和

import java.util.Scanner;public class Main {static final long MOD = 1_000_000_007;public static void main(String[] args){Scanner cin=new Scanner(System.in);long n = cin.nextLong();n = (long) Math.sqrt(n) % MOD; //以此找到对应的n，因为输入的n不是正好被开方/*** 逆元：就是分母移到分子上，相当于补码的转化* 费马小定理运用：k / 6 % MOD = k * pow(6, MOD-2)  */long m = n * (n + 1) % MOD * (2 * n + 1) % MOD * qPow(6, MOD - 2) % MOD; //前n项平方和System.out.println(m);}//快速幂private static long qPow(long a, long n) {long ans = 1;while(n > 0) {if((n & 1) == 1) ans = ans * a % MOD;n >>= 1;a = a * a % MOD;}return ans;}
}