[bzoj 2242]계산기 이산 대수
[토로]
삼 합 일의 템 플 릿 문제.쾌속 멱+확장 gcd+이산 대수
이 세 가 지 를 배 운 사람 은 다 할 수 있 겠 지,아니 야...전송 문:http://www.cnblogs.com/chty/p/6022641.html
쓸 때 손 이 싸 서 하 쉬 시 계 를 잘못 써 서 한참 동안 바 꿨 는데..................................................
못 생 긴 코드 붙 이기:
/*************
bzoj 2242
by chty
2016.11.9
*************/
#include
#include
#include
#include
#include
#include
#include
using namespace std;
#define FILE "read"
#define MAXN 99991
typedef long long ll;
struct node{ll v,f,num;}hash[MAXN+10];
ll a,b,mod;
inline ll read()
{
ll x=0,f=1; char ch=getchar();
while(!isdigit(ch)) {if(ch=='-') f=-1; ch=getchar();}
while(isdigit(ch)) {x=x*10+ch-'0'; ch=getchar();}
return x*f;
}
void insert(ll v,ll x)
{
ll temp=v%MAXN;
while(hash[temp].f&&hash[temp].v!=v) {temp++; if(temp>MAXN) temp-=MAXN;}
if(!hash[temp].f) hash[temp].f=1,hash[temp].v=v,hash[temp].num=x;
}
ll find(ll v)
{
ll temp=v%MAXN;
while(hash[temp].f&&hash[temp].v!=v) {temp++; if(temp>MAXN) temp-=MAXN;}
if(!hash[temp].f) return -1;
else return hash[temp].num;
}
ll gcd(ll a,ll b) {return !b?a:gcd(b,a%b);}
ll exgcd(ll a,ll b,ll &x,ll &y)
{
if(!b) {x=1; y=0; return a;}
ll g=exgcd(b,a%b,x,y);
ll t=x;x=y;y=t-a/b*y;
return g;
}
void solve1(){ll sum=1;for(;b;b>>=1,a=a*a%mod)if(b&1)sum=sum*a%mod;printf("%d
",sum);}
void solve2()
{
ll x,y,d=exgcd(a,mod,x,y);
if(b%d) {printf("Orz, I cannot find x!
");return;}
ll t=mod/d;
while(x<0) x+=t;
while(x>=t) x-=t;
printf("%lld
",x*b%mod);
}
void solve3()
{
if(mod==1) {puts("0"); return;}
a%=mod;b%=mod;
ll ret(1);
for(ll i=0;i<=50;i++) {if(ret==b) {printf("%lld
",i); return; ret=ret*a%mod;}}
ll temp,ans(1),cnt(0);
while((temp=gcd(a,mod))!=1)
{
if(b%temp) {printf("Orz, I cannot find x!
");return;}
mod/=temp; b/=temp;
ans=ans*(a/temp)%mod;
cnt++;
}
ll m=(ll)sqrt(mod*1.0),t(1);
for(ll i=0;i
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 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에 따라 라이센스가 부여됩니다.