首页 > ACM题库 > HDU-杭电 > HDU 2879-HeHe-数论-[解题报告]HOJ
2014
02-17

HDU 2879-HeHe-数论-[解题报告]HOJ

HeHe

问题描述 :

In the equation X^2≡X(mod N) where x∈[0,N-1], we define He[N] as the number of solutions.
And furthermore, define HeHe[N]=He[1]*……*He[N]
Now here is the problem, write a program, output HeHe[N] modulo M for a given pair N, M.

输入:

First line: an integer t, representing t test cases.
Each test case contains two numbers N (1<=N<=10^7) and M (0<M<=10^9) separated by a space.

输出:

First line: an integer t, representing t test cases.
Each test case contains two numbers N (1<=N<=10^7) and M (0<M<=10^9) separated by a space.

样例输入:

1
2 3

样例输出:

2

定义对于正整数n的一个算术函数
f(n),若f(1)=1,且当
a,b互质时f(ab)=f(a)f(b),在数论上就称它为积性函数。若对于某积性函数
f(n) ,就算a, b不互质,也有f(ab)=f(a)f(b),则称它为
完全积性

性质积性函数的值完全由质数的幂决定

常见积性函数:

   φ(n) 欧拉函数,计算与n互质的正整数之数目 

 μ(n) 莫比乌斯函数,关于非平方数的质因子数目

 gcd(n,k) -最大公因子,当k固定的情况 

 d(n) n的正因子数目 

 σ(n) n的所有正因子之和 

 σk(n) - 因子函数,n的所有正因子的k之和,当中k可为任何复数。 

 Idk(n) -幂函数,对于任何复数、实数k,定义为Idk(n) = n^k (完全积性) 

 λ(n) -刘维尔函数,关于能整除n的质因子的数目 

 γ(n),定义为γ(n)=(-1)^ω(n),在此加性函数ω(n)是不同能整除n的质数的数目 

题目:

hdu 2879 HeHe

题意:In the equation X^2≡X(mod N) where x∈[0,N-1], we define He[N] as the number of solutions.

And furthermore, define HeHe[N]=He[1]*……*He[N]

Now here is the problem, write a program, output HeHe[N] modulo M for a given pair N, M.

证明转自http://www.fengshuxin.com/number_theory_hdu_2879.html

1.证明p是素数时He[p]=2.     

 x^2=x(mod p)—->p|x(x-1).因为x<p所以p不整除x也不整除x-1.所以成立的情况下是x=1或者x=0.

He[p^k]=2,证明类似上面的

2.证明对于不同的两个素数p和q,He[p*q]=4=He[p]*He[q];

首先x=0和x=1是肯定成立的,

现在由x^2=x(mod p*q)

       —>p*q|x(x-1)

     假设x=k*p[k<q]

     ——>p*q|k*p(k*p-1)

    ——->q|k(k*p-1)

   ——->q|(k*p-1)  因为k<q  q是素数 所以gcd(k,q)=1

  ——->k*p+t*q=1

 这里就变成了这个方程的解,由扩展欧几里得知,这个方程有解,但是k在[0,q-1]之内的解就一个,所以这里多一个解,同理设x=k*p又有一个解,所以x^2=x(mod p*q)有4个解(x=0 ,x=1 ,x=k*p, x=k*q)

—->He[p*q]=4=He[p]*He[q];

那么He[p1^r1*p2^r2*……*pk^rk]=2^k然后可以进一步算出HeHe只需要算n以内每个素数的倍数的个数.

import java.util.Arrays;
import java.util.Scanner;
public class Main{
	int maxn=10000010,prime[]=new int[maxn];
	boolean isp[]=new boolean[maxn];
	int  getprim(int n)
	{
		int m=1,cnt=0;
		while(m*m<n) m++;
		Arrays.fill(isp,true);
		isp[1]=isp[0]=false;
		prime[++cnt]=2;
		for(int i=4;i<=n;i+=2)
			isp[i]=false;
		for(int i=3;i<=m;i+=2)
			if(isp[i])
			{
				prime[++cnt]=i;
				for(int j=i*i;j<=n;j+=2*i)
					isp[j]=false;
			}
		for(int i=m+1;i<=n;i++)
			if(isp[i])
				prime[++cnt]=i;
		return cnt;
	}
	long mod;
	long fastpow(long n,long p)
	{
		if(p==0)
			return 1;
		long temp=fastpow(n,p/2);
		temp=(temp*temp)%mod;
		if(p%2==0)
			return temp;
		return (temp*n)%mod;
	}
	Scanner scan = new Scanner(System.in);
	void run() {
		int p=getprim(maxn-1);
		int cas=scan.nextInt();
		while(cas-->0){
		long n = scan.nextLong();
		mod=scan.nextLong();
		long cnt=0;
		for(int i=1;i<=p&&prime[i]<=n;i++)
			cnt+=n/prime[i];
		System.out.println(fastpow(2,cnt));
		}
	}

	public static void main(String[] args) {		
		new Main().run();		
		}
}

解题参考:http://blog.csdn.net/kksleric/article/details/8096914


  1. simple, however efficient. A lot of instances it is difficult to get that a??perfect balancea?? among usability and appearance. I must say that youa??ve done a exceptional task with this. Also, the blog masses quite fast for me on Web explore.

  2. Excellent Web-site! I required to ask if I might webpages and use a component of the net web website and use a number of factors for just about any faculty process. Please notify me through email regardless of whether that would be excellent. Many thanks