网站建设公司 预算,html论坛源码,长沙模板建网站需要多久,qq企业邮箱格式P3811 【模板】乘法逆元 一个刚学数论的萌新#xff0c;总结了一下这题的大部分做法 //一、费马小定理快速幂 O(nlogn) 64分
#includecstdio
using namespace std;
typedef long long ll;
int a,b;
inline ll pow(ll x,ll p) {ll ans1;x%b;while(p) {if (p1) an…P3811 【模板】乘法逆元 一个刚学数论的萌新总结了一下这题的大部分做法 //一、费马小定理快速幂 O(nlogn) 64分
#includecstdio
using namespace std;
typedef long long ll;
int a,b;
inline ll pow(ll x,ll p) {ll ans1;x%b;while(p) {if (p1) ansans*x%b;xx*x%b;p1;}return ans%b;
}
inline void write(int x) {if(x9) write(x/10);putchar(x%10^48);
}
int main() {scanf(%d%d,a,b);for (int i1; ia; i) {write(pow(i,b-2));putchar(\n);}
} //二、exgcd O(nlogn) 80分#includecstdio
using namespace std;
typedef int ll;
ll x,y,a,b;
inline void exgcd(ll a,ll b) {if (!b) x1,y0;else {exgcd(b,a%b); int tx; xy,yt-a/b*y;}
}
inline void write(int x){if(x9) write(x/10);putchar(x%10^48);
}
int main() {scanf(%d%d,a,b);for (int i1; ia; i) {exgcd(i,b);write((x%bb)%b);putchar(\n);}
} //三、费马小定理快速幂线性筛 合数O(1)质数O(nlogn) 80分
#include cstdio
using namespace std;
typedef long long ll;
ll n,p,inv[3000010],vis[3000010];
ll pow(ll x,int b) {ll ans1;for (int ib; i; i1,xx*x%p)if (i1) ansans*x%p;return ans%p;
}
void work() {inv[1]vis[1]1;for (int i2; in; i)if (!vis[i]) {vis[i]1;inv[i]pow(i,p-2);for (int j2; ji j*in; j)vis[i*j]1,inv[i*j](inv[i]*inv[j])%p;}
}
int main() {scanf(%lld%lld,n,p);work();for (int i1; in; i) printf(%lld\n,inv[i]);return 0;
} //四、阶乘1次快速幂 O(n) 100分 607ms#includecstdio
#define ll long long
using namespace std;
int n,p;
ll c[3000005],ans[3000005];
ll ksm(ll x,ll y)
{ll an1;while(y){if(y1)an(an*x)%p;x(x*x)%p;y1;}return an;
}
int main()
{scanf(%d%d,n,p);c[0]1;for (int i1;in;i) c[i](c[i-1]*i)%p;ll powksm(c[n],p-2),k;for(int in;i;i--){k(pow*i)%p;ans[i](pow*c[i-1])%p;powk;}for(int i1;in;i)printf(%lld\n,ans[i]);
} //五、线性递推 O(n) 100分 560ms
#includecstdio
#define ll long long
using namespace std;
ll inv[3000005]{0,1};
int main()
{int n,p;scanf(%d%d,n,p);printf(1\n);for (int i2;in;i)printf(%d\n,inv[i](ll)p-(p/i)*inv[p%i]%p);return 0;
} 转载于:https://www.cnblogs.com/Randolph68706/p/11195841.html
