2018.08.30 NOIP模拟 kfib(矩阵快速幂+exgcd)
2024-10-19 21:23:07
【输入】
一行两个整数 n P
【输出】
从小到大输出可能的 k,若不存在,输出 None
【样例输入 1】
5 5
【样例输出】
2
【样例解释】
f[0] = 2
f[1] = 2
f[2] = 4
f[3] = 6 mod 5 = 1
f[4] = 5 mod 5 = 0
f[5] = 1
30%的数据保证 n, P ≤ 1000
100%的数据保证 n, P ≤ 10^9
一道算是比较综合的数论题吧,感觉不是很难。
先用矩阵快速幂求出k=1时f[n]的值。
然后解一个k*f[n]+x*p=1的方程。(考到一半惊奇的发现不能快速幂求逆元233)
代码:
#include<bits/stdc++.h>
#define ll long long
#define a1 a[0][0]
#define a2 a[0][1]
#define a3 a[1][0]
#define a4 a[1][1]
using namespace std;
inline ll read(){
ll ans=0;
char ch=getchar();
while(!isdigit(ch))ch=getchar();
while(isdigit(ch))ans=(ans<<3)+(ans<<1)+(ch^48),ch=getchar();
return ans;
}
ll n,mod;
struct Node{ll a[2][2];Node(){a1=0,a2=a3=a4=1;}};
inline Node operator*(Node a,Node b){
Node ret;
ret.a1=(a.a1*b.a1+a.a2*b.a3)%mod;
ret.a2=(a.a1*b.a2+a.a2*b.a4)%mod;
ret.a3=(a.a3*b.a1+a.a4*b.a3)%mod;
ret.a4=(a.a3*b.a2+a.a4*b.a4)%mod;
return ret;
}
ll ans=0,a,b;
ll Exgcd(ll a,ll b,ll &x,ll &y){
ll ret;
if(!b){
x=1;
y=0;
return a;
}
else{
ret=Exgcd(b,a%b,x,y);
ll t=x;x=y;y=t-(a/b)*y;
return ret;
}
}
ll equa(ll a,ll b,ll c,ll & x,ll y){
ll d=Exgcd(a,b,x,y);
if(c%d)return 0;
ll k=c/d;
x*=k;y*=k;
ans=(x%(b/d)+b/d)%(b/d);
return 1;
}
inline Node ksm(ll p){
Node x,ret;
while(p){if(p&1)ret=ret*x;x=x*x,p>>=1;}
return ret;
}
inline ll gcd(ll a,ll b){while(b){ll t=a;a=b,b=t%a;}return a;}
int main(){
freopen("kfib.in","r",stdin);
freopen("kfib.out","w",stdout);
n=read(),mod=read();
Node ttmp=ksm(n-2);
ll tmp=(ttmp.a2+ttmp.a4)%mod;
if(!tmp){puts("None");return 0;}
if(gcd(tmp,mod)!=1){puts("None");return 0;}
ll x,y;
equa(tmp,mod,1,x,y);
cout<<ans;
return 0;
}
最新文章
- .htaccess下Flags速查表
- Netty的TCP粘包/拆包(源码二)
- Java数组的一些基本算法
- css015 定位网页上的元素
- LA 3523 圆桌骑士
- jQery简单Tab选项卡效果
- yii 隐藏index.php的步骤
- 【转】Log4.NET mark
- iOS 启动连续闪退保护方案
- Embedded tomcat 7 servlet 3.0 annotations not working--转
- HDU 2159 FATE(全然背包+二维费用背包)
- 编程算法 - 圆圈中最后剩下的数字(递推公式) 代码(C++)
- WAMP多站点配置,更改服务器端口
- HTML5获取当前的经纬度坐标
- NAT穿透的详解及分析
- Android中在不同activity中进行自定义广播的解析
- vmware 挂起后不能恢复
- getElementById和$()获取值一点注意事项
- Spring Boot中Web应用的统一异常处理 转载来自翟永超
- Global Illumination