hdu4059容斥原理

本文主要是介绍hdu4059容斥原理，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

求1-n中与n互质的数的4次方之和

import java.io.BufferedInputStream;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.io.StreamTokenizer;
import java.util.ArrayList;
import java.util.StringTokenizer;public class Main {public static void main(String[] args) throws IOException {StreamTokenizer cin = new StreamTokenizer(new BufferedInputStream(System.in));InputReader in = new InputReader(System.in);PrintWriter out = new PrintWriter(System.out);int t = in.nextInt();for (int i = 1; i <= t; i++) {// out.print("Case " + i + ": ");new Task().solve(in, out);}out.flush();}}class Task {static long MOD = 1000000007L;static int N = 10000;static boolean[] vis = new boolean[N + 1];static int[] prime = new int[N + 1];static int pid = 0;static {for (int i = 2; i <= N; i++) {if (!vis[i])prime[pid++] = i;for (int j = 0; j < pid && i * prime[j] <= N; j++) {vis[j] = true;if (i % prime[j] == 0)break;}}}ArrayList<Integer> factor = new ArrayList<Integer>();long n;static long pow(long x, int y) {long s = 1;for (; y > 0; y >>= 1) {if ((y & 1) > 0) {s = s * x % MOD;}x = x * x % MOD;}return s;}static long thirty = pow(30L, (int) MOD - 2);long sigmasum4(long k) {long sum = k * (k + 1) % MOD;long t = (6L * pow(k, 3) % MOD + 9L * pow(k, 2) % MOD) % MOD;t = (t + k - 1) % MOD;t = (t + MOD) % MOD;sum = sum * t % MOD;sum = sum * thirty % MOD;return sum;}long answer() {long ans = sigmasum4(n);int m = factor.size();int limit = 1 << m;for (int i = 1; i < limit; i++) {int k = 0;long val = 1;for (int j = 0; j < m; j++) {if ((i & (1 << j)) > 0) {k++;val *= factor.get(j);}}long sum = pow(val, 4) * sigmasum4(n / val) % MOD;if ((k & 1) > 0)ans = ((ans - sum) % MOD + MOD) % MOD;elseans = (ans + sum) % MOD;}return ans;}public void solve(InputReader in, PrintWriter out) throws IOException {n = in.nextLong();long m = n;for (int i = 0; i < pid && prime[i] * prime[i] <= m; i++) {if (m % prime[i] == 0) {while (m % prime[i] == 0)m /= prime[i];factor.add(prime[i]);}}if (m != 1)factor.add((int) m);out.println(answer());}}class InputReader {public BufferedReader reader;public StringTokenizer tokenizer;public InputReader(InputStream stream) {reader = new BufferedReader(new InputStreamReader(stream), 32768);tokenizer = null;}public String next() {while (tokenizer == null || !tokenizer.hasMoreTokens()) {try {tokenizer = new StringTokenizer(reader.readLine());} catch (IOException e) {throw new RuntimeException(e);}}return tokenizer.nextToken();}public int nextInt() {return Integer.parseInt(next());}public long nextLong() {return Long.parseLong(next());}public double nextDouble() {return Double.parseDouble(next());}}

这篇关于hdu4059容斥原理的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---