hdu6053 TrickGCD 莫比乌斯反演

本文主要是介绍hdu6053 TrickGCD 莫比乌斯反演，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

TrickGCD

Time Limit: 5000/2500 MS (Java/Others) Memory Limit: 262144/262144 K (Java/Others)

Problem Description

You are given an array

A , and Zhu wants to know there are how many different array

B satisfy the following conditions?

*

1≤Bi≤Ai
* For each pair( l , r ) (

1≤l≤r≤n ) ,

gcd(bl,bl+1...br)≥2

Input

The first line is an integer T(

1≤T≤10 ) describe the number of test cases.

Each test case begins with an integer number n describe the size of array

A .

Then a line contains

n numbers describe each element of

A

You can assume that

1≤n,Ai≤105

Output

For the

k th test case , first output "Case #k: " , then output an integer as answer in a single line . because the answer may be large , so you are only need to output answer

mod

109+7

Sample Input

  1
4
4 4 4 4

Sample Output

  Case #1: 17

Source

2017 Multi-University Training Contest - Team 2

import java.io.BufferedReader;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.math.BigInteger;
import java.util.Arrays;
import java.util.StringTokenizer;public class Main {public static void main(String[] args) {new Task().solve();}
}class Task {InputReader in = new InputReader(System.in) ;PrintWriter out = new PrintWriter(System.out) ;final long Mod = 1000000007L ;final int N = 100000 ;int[] mu = new int[N+1] ;int[] prime = new int[N+1] ;boolean[] vis = new boolean[N+1] ;{int cnt = 0 ;Arrays.fill(vis, false);mu[1] = 1 ;for(int i = 2 ; i <= N ; i++){if(! vis[i]){prime[cnt++] = i ;mu[i] = -1 ;}for(int j = 0 ; j < cnt && i * prime[j] <= N ; j++){vis[i * prime[j]] = true ;if(i % prime[j] == 0){mu[i * prime[j]] = 0 ;break ; }mu[i * prime[j]] = -mu[i] ;}}}long pow(long x , int y){long s = 1 ;for(; y > 0 ; y >>= 1){if((y & 1) > 0){s *= x ;s %= Mod ;}x *= x ;x %= Mod ;}return s ;}void solve(){int t = in.nextInt() ; for(int cas = 1 ; cas <= t ; cas++){int[] sum = new int[2*N+1] ;int _min = Integer.MAX_VALUE ;int _max = Integer.MIN_VALUE ;long all = 1 ;Arrays.fill(sum, 0) ;int n = in.nextInt() ;int[] a = new int[n+1] ;for(int i = 1 ; i <= n ; i++){a[i] = in.nextInt() ;_min = Math.min(_min , a[i]) ;_max = Math.max(_max, a[i]) ;sum[a[i]]++ ;all *= a[i] ;all %= Mod ;}for(int i = 1 ; i <= 2*N ; i++){sum[i] += sum[i-1] ;}long _all = 0 ;for(int d = 1 ; d <= _min ; d++){long h = (mu[d] + Mod) % Mod ;for(int g = 1 ; g <= _max/d ; g++){int cnt = sum[d*(g+1)-1] - sum[d*g-1] ;h *= pow(g, cnt) ;h %= Mod ;}_all += h ;_all %= Mod ;}all -= _all ;all %= Mod ;all = (all + Mod) % Mod ;out.println("Case #"+ cas + ": " + all) ;}out.flush() ;}}class InputReader {    public BufferedReader reader;    public StringTokenizer tokenizer;    public InputReader(InputStream stream) {    reader = new BufferedReader(new InputStreamReader(stream), 32768);    tokenizer = new StringTokenizer("");    }    private void eat(String s) {    tokenizer = new StringTokenizer(s);    }    public String nextLine() {     try {    return reader.readLine();    } catch (Exception e) {    return null;    }    }    public boolean hasNext() {    while (!tokenizer.hasMoreTokens()) {    String s = nextLine();    if (s == null)    return false;    eat(s);    }    return true;    }    public String next() {    hasNext();    return tokenizer.nextToken();    }    public int nextInt() {    return Integer.parseInt(next());    }    public int[] nextInts(int n) {    int[] nums = new int[n];    for (int i = 0; i < n; i++) {    nums[i] = nextInt();    }    return nums;    }    public long nextLong() {    return Long.parseLong(next());    }    public double nextDouble() {    return Double.parseDouble(next());    }    public BigInteger nextBigInteger() {    return new BigInteger(next());    }    }

这篇关于hdu6053 TrickGCD 莫比乌斯反演的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！