線性丟番圖方程
ax+by=c
d=gcd(a,b)，若c|d，有無窮整數解 x = x 0 + b d n , y = y 0 ? a d n x=x_0+{b\over d}n,y=y_0-{a\over d}n x=x0?+db?n,y=y0??da?n
POJ 1265
poj真難用，abs一直報錯，萬能頭也不能用，給我調紅溫了
struct point
{int x,y;
} q[1010];
int n;
ll num,In;
double S;
int gcd(int A,int B)
{return B==0?A:gcd(B,A%B);
}
int Mult(point A,point B)
{return A.x*B.y-B.x*A.y;
}
int main()
{int T,xx,yy,sx,sy,dx,dy,K=0;scanf("%d",&T);while(T--){scanf("%d",&n);sx=sy=0;S=0;num=0;for(int i=1; i<=n; i++){scanf("%d%d",&xx,&yy);sx+=xx;sy+=yy;q[i].x=sx;q[i].y=sy;}q[0].x=q[n].x;q[0].y=q[n].y;for(int i=0; i<n; i++){S+=Mult(q[i],q[i+1]);dx=abs(q[i].x-q[i+1].x);dy=abs(q[i].y-q[i+1].y);num+=gcd(max(dx,dy),min(dx,dy));}S=fabs(S/2);//不確定S是否為正數In=int(S)+1-num/2;//pick定理：點陣中 面積 = 內部格點數 + 邊界格點數/2 - 1printf("Scenario #%d:\n",++K);printf("%I64d %I64d %.1f\n\n",In,num,S);}return 0;
}
擴展歐幾里得算法
給 a x + b y = c ax+by=c ax+by=c找到一個特解
const int N=3e6+10;
int inv[N];
void solve(){int n,p;cin>>n>>p;inv[1]=1;cout<<inv[1]<<endl;forr(i,2,n){inv[i]=(p-p/i)*inv[p%i]%p;cout<<inv[i]<<endl;}
}
求逆
模意義下的乘法逆元
遞推求1~n的模p的逆
1 ? 1 = 1 若 p / k = i . . . r ，那么 k i + r ≡ 0 ( m o d p ) ( p / i ) r ? 1 + i ? 1 ≡ 0 ( m o d p ) i ? 1 ≡ ? ( p / i ) r ? 1 ( m o d p ) i ? 1 ≡ ( p ? p / i ) r ? 1 ( m o d p ) 1^{-1}=1 \\ 若p/k=i...r，那么ki+r\equiv 0(mod\ \ p)\\ (p/i)r^{-1}+i^{-1}\equiv 0(mod\ \ p)\\ i^{-1}\equiv -(p/i)r^{-1}(mod\ \ p)\\ i^{-1}\equiv (p-p/i)r^{-1}(mod\ \ p) 1?1=1若p/k=i...r，那么ki+r≡0(mod??p)(p/i)r?1+i?1≡0(mod??p)i?1≡?(p/i)r?1(mod??p)i?1≡(p?p/i)r?1(mod??p)
const int N=3e6+10;
int inv[N];
void solve(){int n,p;cin>>n>>p;inv[1]=1;cout<<inv[1]<<endl;forr(i,2,n){inv[i]=(p-p/i)*inv[p%i]%p;cout<<inv[i]<<endl;}
}
gcd
P1029最大公約數和最小公倍數問題
x y = P Q , g c d ( P , Q ) = x , l c m ( P , Q ) = y xy=PQ,gcd(P,Q)=x,lcm(P,Q)=y xy=PQ,gcd(P,Q)=x,lcm(P,Q)=y
給出xy，求出P Q對數
枚舉
void solve()
{int x,y;cin>>x>>y;int a=x*y;int ans=0;for(int i=1;i*i<=a;i++){//枚舉P Qif(a%i==0&&__gcd(i,a/i)==x)ans+=(i==a/i?1:2);//注意完全平方數 是一個情況}cout<<ans<<endl;
}
P10426
裴屬定理
a x + b y = k gcd ? ( a , b ) ax+by=k\gcd(a,b) ax+by=kgcd(a,b)
P4549
A 1 x 1 + A 2 x 2 + A 3 x 3 = k gcd ? ( A 1 , A 2 ) + A 3 x 3 = k ′ gcd ? ( A 1 , A 2 , A 3 ) A_1x_1+A_2x_2+A_3x_3=k\gcd(A_1,A_2)+A_3x_3=k'\gcd(A_1,A_2,A_3) A1?x1?+A2?x2?+A3?x3?=kgcd(A1?,A2?)+A3?x3?=k′gcd(A1?,A2?,A3?)
void solve()
{int n;cin>>n;vector<int>a(n+1);forr(i,1,n){cin>>a[i];}int s=0;s=__gcd(a[1],a[2]);for(int i=3;i<=n;i++){s=__gcd(a[i],s);}cout<<abs(s)<<endl;
}
素數
位運算
P1469
相同的數兩兩異或得0
void solve()
{int n;cin>>n;int ans=0;forr(i,1,n){int a;cin>>a;ans=ans^a;// cout<<ans<<' ';}cout<<ans<<endl;
}
.openEndDrawer()；不生效問題)
