[BZOJ] [P1965] [AHOI 2005] [SHUFPLE 카드 세탁] [문제 풀이] [수론]
http://www.lydsy.com/JudgeOnline/problem.php?id=1965
군 론 인 줄 알 았 는데.............................................................
나중에 보 니 수론 이 었 는데..................................................
x* 2^m=l (mod n+1)
풀다
빠 른 속도 + 0 ms 확장 초 살...
Code：
#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long lld;
lld n,m,l;
lld exgcd(lld a,lld b,lld &x,lld &y){
if(!b){
x=1;y=0;
return a;
}else{
lld g=exgcd(b,a%b,x,y);
lld t=x;
x=y;
y=t-a/b*y;
return g;
}
}
lld gcd(lld a,lld b){
while(b){
lld t=a;
a=b;
b=t%b;
}
return a;
}
lld power(lld x,lld k){
lld ans=1;
for(;k;k>>=1){
if(k&1)ans*=x;
x*=x;
if(x>n)x%=(n+1);
if(ans>n)ans%=(n+1);
}
return ans;
}
int main(){
cin>>n>>m>>l;
m=power(2,m);
//x*m=l(mod n+1)
//mx + (n+1) y =l
//m'x+(n+1)' y=l'
lld x,y;
n=n+1;
lld d=gcd(m,n);
m/=d;n/=d;l/=d;
exgcd(m,n,x,y);
x=x*l%n;
while(x<0)x+=n;
cout<<x<<endl;
return 0;
}이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
bzoj1010 장난감 포장 [결정 단조성 최적화 dp]하나의 모범 문제라고 할 수 있다.우리는 먼저 소박한 dp방정식을 얻을 수 있다. f[i]=min(f[j]+w(j,i)),j∈[0,i). w(j,i)는 j+1~i를 포장하여 운송하는 비용의 시간 복잡도는 O(n2)라...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
