这个题是必须用拓欧吗
查看原帖
这个题是必须用拓欧吗
1536649
dingzhen11楼主2025/7/25 19:52
#include<iostream>
using namespace std;
#define ull unsigned long long
ull fastpow(ull a,ull b,ull p){
	ull sum=1;
	while(b>=1){
		if(b&1){
			sum*=a;
			b--;
			sum%=p;
		}
		a=a*a;
    a%=p;
		b/=2;
	}
	return sum;
}//常规快速幂
int main(){
	ull n=11,p=3;
	cin>>n>>p;
	for(ull i=1;i<=n;i++){
		//a^(p-1) mod p=1 mod p;
		//费马小定理 
		cout<<fastpow(i,p-2,p)<<"\n";
	}
	return 0;
}

各位大佬,以上是我的代码,TLE最后一个点, 这是本蒟蒻想到的最快的使用费马小定理的代码了,复杂度为O(nlogn)O(n log n)

所以,求助大佬们,这个代码还可以优化吗?

2025/7/25 19:52
加载中...