快读!快写!快速幂!!!费马小定理,还要多快最后两个点才不会TLE
查看原帖
快读!快写!快速幂!!!费马小定理,还要多快最后两个点才不会TLE
677150
ThEskY_B1ackeR楼主2023/2/2 19:44
#include<bits/stdc++.h>
using namespace std;

long long p;

long long Quick_Pow(long long a,long long b){
	
	long long sum=1;
	
	while(b){
	
		if(b%2==1)sum=sum*a%p;
	
		a=a*a%p;
	
		b/=2;
	}
	
	return sum;
} 

void read(long long& a){
	
	char ch;
	
	bool flag=true;
	
	do{
		
		ch = getchar();
		
		if(ch == '-')flag=false;
		
	}while(ch<'0'||ch>'9');
	
	a=0;
	
	while(ch>='0'&&ch<='9'){
		
		a=a*10+ch-'0';
		
		ch = getchar();
		
	}
	
	if(!flag) a=-a;
						
} 

void write(int a){
	
	if(a<0){
		
		putchar('-');
		
		a=-a;
		
	}
	
	if(a>=10)
	
		write(a/10);
		
	putchar(a%10+'0');
	
} 
int main(){
	
	long long n;
	
	read(n);read(p);
	
	for(long long i=1;i<=n;i++){ write(Quick_Pow(i,p-2)%p); putchar('\n');}
	
	return 0;
}
2023/2/2 19:44
加载中...