题面：https://www.cnblogs.com/Juve/articles/11639923.html
simple：
考试时只想到的暴力exgcd判断
考虑n，m互质的情况：
我们枚举y，对于方程$n*x+m*y leq q$，$xleqfrac{q-m*y}{n}$
其中y的范围是[0,n-1]，因为如果y大于n-1，那么可以使x的系数加一，会有重复
然后如果n，m不互质，那么设$n=n'*gcd(n,m),m=m'*gcd(n,m)$，所以$n'*gcd(n,m)*x+m'*gcd(n,m)*y leq q$
其中把$gcd(n,m)*y$看成一个整体，那么枚举y的范围要保证$gcd(n,m)*yin[0,n-1]$
然后就A了
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<algorithm> 5 #define int long long 6 using namespace std; 7 const int MAXN=1e5+5; 8 int t,n,m,q,ans; 9 int gcd(int a,int b){ 10 return b==0?a:gcd(b,a%b); 11 } 12 int max(int a,int b){return a>b?a:b;} 13 signed main(){ 14 scanf("%lld",&t); 15 while(t--){ 16 scanf("%lld%lld%lld",&n,&m,&q); 17 int g=gcd(n,m); 18 ans=0; 19 for(int i=0;i<(n/g);++i){ 20 int x=q-i*m; 21 if(x<0) break; 22 ans+=x/n+1; 23 } 24 printf("%lld ",q-(ans-1)); 25 } 26 return 0; 27 }
walk：
枚举gcd，然后把边权是gcd倍数的边建出来，形成一个森林，求出森林的直径即是答案为gcd时的边的长度
注意一点，有些长度可能不会出现在最长链中，因为他是构成最长链的一部分，所以如果这个长度的答案<长度大于他的答案的话，就要将长度大于他的答案给他，从大到小枚举ans[i]=max(ans[i],ans[i+1]).
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#include<queue>
using namespace std;
const int MAXN=4e5+5;
const int MAXM=1e6+5;
int n,maxx=0,res[MAXN],len=0;
vector< pair<int,int> >e[MAXM];
int to[MAXN<<1],nxt[MAXN<<1],pre[MAXN],cnt=0;
void add(int u,int v){
++cnt,to[cnt]=v,nxt[cnt]=pre[u],pre[u]=cnt;
}
bool vis[MAXN];
int sta[MAXM],top=0;
int dfs(int x,int fa){
vis[x]=1;
int l=0,r=0;
for(int i=pre[x];i;i=nxt[i]){
int y=to[i];
if(y==fa||vis[y]) continue;
int p=dfs(y,x);
if(p+1>l) r=l,l=p+1;
else if(p+1>r) r=p+1;
}
len=max(len,l+r);
return l;
}
int main(){
scanf("%d",&n);
for(int i=1,u,v,w;i<n;++i){
scanf("%d%d%d",&u,&v,&w);
maxx=max(maxx,w);
e[w].push_back(make_pair(u,v));
}
for(int i=1;i<=maxx;++i){
cnt=0;
for(int j=i;j<=maxx;j+=i){
int N=e[j].size();
for(int k=0;k<N;++k){
int u=e[j][k].first,v=e[j][k].second;
add(u,v),add(v,u);
sta[++top]=u,sta[++top]=v;
}
}
for(int j=1;j<=top;++j){
if(!vis[sta[j]]){
len=0;
dfs(sta[j],0);
res[len]=max(res[len],i);
}
}
for(int j=1;j<=top;++j){
pre[sta[j]]=vis[sta[j]]=0;
}
top=0;
}
for(int i=n-1;i>=1;--i) res[i]=max(res[i],res[i+1]);
for(int i=1;i<=n;++i) printf("%d
",res[i]);
return 0;
}
棋盘：
容斥一发推式子：
$ans=sumlimits_{i=2}^{n}(-1)^i*A_{n}^{i}$
再加个高精度
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<algorithm> 5 #define re register 6 using namespace std; 7 const int MAXN=205; 8 int n,mp[MAXN][MAXN]; 9 struct bigint{ 10 int m[1005]; 11 inline friend bigint operator * (re bigint a,re int b){ 12 re int x=0; 13 for(re int i=1;i<=a.m[0];i++){ 14 re int y=a.m[i]*b+x; 15 a.m[i]=y%10; 16 x=y/10; 17 } 18 while(x){ 19 a.m[++a.m[0]]=x%10; 20 x/=10; 21 } 22 return a; 23 } 24 inline friend void operator += (re bigint &a,re bigint b){ 25 a.m[0]=max(a.m[0],b.m[0])+1; 26 for(re int i=1;i<=a.m[0];++i) 27 a.m[i]+=b.m[i]; 28 for(re int i=1;i<=a.m[0];++i) 29 if(a.m[i]>9) a.m[i]-=10,++a.m[i+1]; 30 while(a.m[0]!=1&&a.m[a.m[0]]==0) 31 --a.m[0]; 32 } 33 inline friend bigint operator - (re bigint a,re bigint b){ 34 re bigint c; 35 re int i=1; 36 while((i<=a.m[0])||(i<=b.m[0])){ 37 if(a.m[i]<b.m[i]){ 38 a.m[i]+=10; 39 a.m[i+1]--; 40 } 41 c.m[i]=a.m[i]-b.m[i]; 42 i++; 43 } 44 while(c.m[i]==0&&i>1) 45 i--; 46 c.m[0]=i; 47 return c; 48 } 49 inline friend bigint operator * (re bigint a,re bigint b){ 50 re bigint c; 51 memset(c.m,0,sizeof(c.m)); 52 c.m[0]=a.m[0]+b.m[0]+10; 53 for(re int i=1;i<=a.m[0];++i){ 54 for(re int j=1;j<=b.m[0];++j){ 55 c.m[i+j-1]+=a.m[i]*b.m[j]; 56 } 57 } 58 for(re int i=1;i<=c.m[0];++i){ 59 if(c.m[i]>9) c.m[i+1]+=c.m[i]/10,c.m[i]%=10; 60 } 61 while(c.m[0]!=1&&c.m[c.m[0]]==0) --c.m[0]; 62 return c; 63 } 64 }fac[MAXN],C[MAXN][MAXN],ans; 65 inline void print(bigint a){ 66 for(re int i=a.m[0];i>=1;--i){ 67 printf("%d",a.m[i]); 68 } 69 puts(""); 70 } 71 signed main(){ 72 //freopen("test.in","r",stdin); 73 //freopen("ans.out","w",stdout); 74 scanf("%d",&n); 75 for(re int i=1;i<=n;++i){ 76 for(re int j=1,k;j<=n;++j){ 77 scanf("%d",&k); 78 mp[i][j]=k; 79 } 80 } 81 fac[0].m[0]=fac[0].m[1]=1; 82 for(re int i=1;i<=n;++i) fac[i]=fac[i-1]*i; 83 C[0][0].m[0]=C[0][0].m[1]=1; 84 for(re int i=1;i<=n;++i){ 85 C[i][0].m[0]=C[i][0].m[1]=1; 86 for(re int j=1;j<=i;++j){ 87 C[i][j]=C[i-1][j]; 88 C[i][j]+=C[i-1][j-1]; 89 //C[i][j]=C[i-1][j]+C[i-1][j-1]; 90 } 91 } 92 /*for(int i=1;i<=n;++i){ 93 for(int j=0;j<=i;++j){ 94 print(C[i][j]); 95 } 96 puts(""); 97 }*/ 98 ans=fac[n]; 99 for(re int i=1;i<=n;++i){ 100 if(i&1) ans=ans-C[n][i]*fac[n-i]; 101 else ans+=C[n][i]*fac[n-i]; 102 //ans+=C[n][i]; 103 } 104 print(ans); 105 return 0; 106 }