Tìm số nghiệm x thuộc [1,b] thỏa mãn x^2 đồng dư 1 mod p

[DDD]

SPOJ.com - Problem CPPMOD08

#include<iostream>
#include<cmath>
using namespace std;
int dem(int b, int p){
	if(b*b<p) return 1;
	if(p==1) return (b+1);
	//tim uoc nguyen to lon nhat cua p <=> buoc nhay
	int temp=p,jump=1;
	for(int i=2;i<=p;i++){
		while(temp%i==0){
//			cout<<"temp="<<temp<<endl;
			if((temp/i)==1){
				jump=temp;
				break;
			} 
			temp/=i;
		}
	}
//	cout<<"jump="<<jump<<endl;
	
	if(jump==2){
		int start=sqrt(p)/jump+1;
//	cout<<"start="<<start<<endl;
	//TH =1 luon dung
	int count=1;
	for(int i=start*jump;i<=b+1;i+=jump){
//		cout<<"i="<<i<<endl;
		if(i*(i-2)%p==0 ){
			count++;
//			cout<<"if: "<<count<<endl;
		}
		
	}
	return count;
	}
	else{
	//tim diem bat dau
	int start=sqrt(p)/jump+1;
//	cout<<"start="<<start<<endl;
	//TH =1 luon dung
	int count=1;
	for(int i=start*jump;i<=b+1;i+=jump){
//		cout<<"i="<<i<<endl;
		if(i*(i-2)%p==0 ){
			count++;
		}
			
		if(i*(i+2)%p==0 && i+2<=b+1 ){
			count++;
		}
	
	}
	return count;
}
}
int main(){
	int t; cin>>t;
	while(t--){
		int b,p;
		cin>>b>>p;
		
		cout<<dem(b,p)<<endl;
		
	}
}

Ý tưởng:

• x^2-1 chia hết cho p => (x-1)(x+1) chia hết cho p
  => x-1 or x+1 chia hết cho ước nguyên tố lớn nhất của p
  => Tìm ước nguyên tố lơn nhất của p để nhảy
• Trường hợp đặc biệt p==1 và ước nguyên tố lớn nhất là 2

Code em làm theo ý tưởng như trên nộp hệ thống nó báo sai test cuối ai biết trường họp nào em chưa xét đến không ạ ? @@
Cảm ơn mọi người nhiều !

[rogp10]

Chắc thiếu nghiệm rồi với lại trường hợp số 2 nữa. Bài này chạy trâu cũng O(p) thôi.

[DDD]

#include<iostream>
#include<cmath>
using namespace std;
int dem(int b, int p){
	if(b*b<p) return 1;
	int count=1;
	for(int i=sqrt(p);i<=b;i++){
		if((i*i-1)%p==0)
			count++;
	}
	return count;
}
int main(){
	int t; cin>>t;
	while(t--){
		int b,p;
		cin>>b>>p;
		
		cout<<dem(b,p)<<endl;
	}
}

bài này e chạy chay kiểu này thì bị quá thời gian @rogp10

[rogp10]

Code bạn là O(b) mà khác chứ.

Một số kết quả:

• Nếu modulo p là lũy thừa của số nguyên tố lẻ thì phương trình (mod p) chỉ có hai nghiệm tầm thường (ko tính tiền ) xét p | (x-1)(x+1), nếu p chia hết cả hai thừa số thì p chia hết 2 (vô lí).
• Nếu modulo p là lũy thừa của 2 và >= 8 thì phương trình (mod p) có 4 nghiệm, nếu p = 4 thì có 2 nghiệm +/-1.
• Nếu modulo là hợp số lẻ kiểu q^a*r^b*s^c*... ta lập 2 lũy thừa (số thừa số nguyên tố) hệ đồng dư để giải (do các thừa số đôi một nguyên tố cùng nhau ). Thực ra không lớn vì 13# = 30030 nên cao nhất là 6 thừa số, O(sqrt(p)).
• Tương tự với hợp số chẵn.

nguồn: http://math.bu.edu/people/dmm/341/Handouts/sqrts-one-modm.pdf