Record My Thoughts
【算法分析】
在纸上玩一下可以发现：
1、假设他们是两两配对的，那么，一个人取了以后，那么另一个人必然可以通过一种方案使得他仍然配对。所以后手必胜。
2、如果他们不是两两配对的，那么先取者必然可以通过弄数量最大的那一组使得他们变成两两配对，这样，自己就可以赢了。
所以，我们只需判断它给的是否两两配对。
【其他】1A
5/8个男人。。。
【CODE】
#include
int n,i,ans;
int a[10];
int main(){
while (1){
cin >> n;
if (!n) break;
for (i=0;i
ans=0;
if (!(n&1)){
for (i=0;i
cout << ans << endl;
}
else cout << 1 << endl;
}
}
【题目大意】找一个特殊图哈密顿回路的方案数。
【算法分析】
我先DFS了一下，感觉如果列是4的话，应该是一个4阶的递归式。
然后找到规律。。。OH,YEAH，AC
规律就是F[n]=2F[n-1]+2F[n-2]-2F[n-3]+F[n-4]
【其它】1A
【CODE】
/*
ID:jie22221
TASK:vans
LANG:C++
*/
#include
const int Mod=100000;
struct bigint{int d[M+1];};
int px[4]={-1,1,0,0},py[4]={0,0,1,-1};
int n,limit,total,ans;
bigint f[1001];
bool v[5][5];
void dfs(int x,int y){
if (total==4*limit-1){
if (x+y==3) ans++;
return;
}
int k,tx,ty;
v[x][y]=true;
total++;
for (k=0;k<4;k++){
tx=x+px[k]; ty=y+py[k];
if (tx<1 || tx>4 || ty<1 || ty>limit || v[tx][ty]) continue;
dfs(tx,ty);
}
v[x][y]=false;
total–;
}
bigint plus(bigint x,bigint y){
for (int i=1;i<=M;i++) x.d[i]+=y.d[i];
for (int i=M;i>=1;i–){
x.d[i-1]+=x.d[i]/Mod;
x.d[i]%=Mod;
}
return x;
}
bigint dec(bigint x,bigint y){
for (int i=1;i<=M;i++) x.d[i]-=y.d[i];
for (int i=M;i>=1;i–)
while (x.d[i]<0){
x.d[i]+=Mod;
x.d[i-1]–;
}
return x;
}
void init(){
memset(f,0,sizeof(f));
for (limit=1;limit<=4;limit++){
ans=0;
total=0;
dfs(1,1);
f[limit].d[M]=ans;
}
}
void put(bigint x){
int st;
for (st=0;st<=M;st++)
if (x.d[st]) break;
printf("%d",x.d[st]);
for (int i=st+1;i<=M;i++){
int div=Mod/10,mod=Mod;
while (div>0){
printf("%d",x.d[i]%mod/div);
mod/=10;
div/=10;
}
}
printf("n");
}
void work(){
scanf("%d",&n);
if (n<=4){
printf("%dn",f[n].d[M]);
return;
}
bigint tmp;
for (int i=5;i<=n;i++){
memset(tmp.d,0,sizeof(tmp.d));
tmp=plus(f[i-1],f[i-1]);
f[i]=plus(f[i],tmp);
tmp=plus(f[i-2],f[i-2]);
f[i]=plus(f[i],tmp);
tmp=plus(f[i-3],f[i-3]);
f[i]=dec(f[i],tmp);
f[i]=plus(f[i],f[i-4]);
}
put(f[n]);
}
int main(){
freopen("vans.in","r",stdin);
freopen("vans.out","w",stdout);
init();
work();
}
【题目大意】
给定x和a0的最大公约数是a1
x和b0的最小公倍数是b1
求存在多少个符合条件的x
【算法分析】
哎，NOIP第2题，当时只拿50分。。。
在景润后人的指导下，发现原来这么简单。。。原来我当时捉错方向了。
题目相当于给出两个条件：
根据第一个条件去构造的话，只能根据x=k*a0直接枚举。极限数据的话这必然TLE。
然后如果根据第二个条件去构造的话，就可以根据质因子来dfs，虽然也比较暴力，但是明显比上面那个好很多。。。
于是我们可以对b0质因数分解，枚举构造b0/gcd(b0,x)的这个部分，然后再用b1得到x，再判定就行了。
【其它】TLE多次，最终分解质因数那里改了一下，终于AC。
YM best user 景润后人 AekdyCoin
95562 AekdyCoin 2080 Accepted GNU C++ 1.46k 40ms 1312KB 2009-11-22 14:39:10 95729 xiaotian 2080 Accepted Free Pascal 3.39k 60ms 416KB 2009-11-24 13:31:02 96022 nehzilrz(2) 2080 Accepted GNU C++ 1.10k 60ms 768KB 2009-11-28 11:08:08 99216 edward 2080 Accepted GNU C++ 1.36k 60ms 1536KB 2010-02-12 18:22:38
【CODE】
#include
int ss[N],a0,a1,b0,b1,ssl[N],sst;
int sl[N],num[N],len,ans;
int gcd(int x,int y){
if (y==0) return x;
return gcd(y,x%y);
}
void makess(){
sst=0;
ss[1]=1;
for (int i=2;i*i<=N;i++) if (!ss[i])
for (int j=i;i*j<=N;j++)
ss[i*j]=1;
for (int i=1;i<=N;i++)
if (ss[i]==0){
sst++;
ssl[sst]=i;
}
}
void fenjie(int n){
len=0;
for (int i=1;n!=1 && n>=ssl[i] && i<=sst;i++)
if (n%ssl[i]==0){
len++;
sl[len]=ssl[i];
num[len]=0;
while (n%ssl[i]==0){
n/=ssl[i];
num[len]++;
}
}
if (n!=1){
len++;
sl[len]=n;
num[len]=1;
}
}
void dfs(int i,int now){
if (i>len){
int x=b1/now;
int t=gcd(x,b0),tmp=x/t*b0;
if (gcd(x,a0)!=a1 || x/gcd(x,b0)*b0!=b1) return;
ans++;
return;
}
dfs(i+1,now);
for (int k=1;k<=num[i];k++){
now*=sl[i];
dfs(i+1,now);
}
}
int main(){
makess();
int tc;
scanf("%d",&tc);
for (int i=1;i<=tc;i++){
scanf("%d%d%d%d",&a0,&a1,&b0,&b1);
fenjie(b0);
ans=0;
dfs(1,1);
printf("%dn",ans);
}
}
【题目大意】
an = X*an-1 + Y 保证 y mod (x-1)=0
求最小的Ak mod a0=0
【算法分析】
先用等比数列求和公式得到通项。
最后推导出求x^k = 1 (mod a0)，然后再利用欧拉函数求解。
具体看这里吧
http://hi.baidu.com/aekdycoin/blog/item/e5224da98d6c2fbaca130c67.html
后面的欧拉函数部分还不是很懂。。。
【CODE】
#include
__int64 x,y,a0;
__int64 phi(__int64 a){
__int64 r=a;
for (__int64 i=2;i<=a/i;i++)
if(a%i==0){
r-=r/i;
while(a%i==0)
a/=i;
}
return a<2?r:r-r/a;
}
__int64 gcd(__int64 a,__int64 b){
if (b==0) return a;
return gcd(b,a%b);
}
__int64 mod(__int64 a,__int64 b,__int64 c){
__int64 r=1%c;
while(b){
if(b&1)r=r*a%c;
a=a*a%c;
b=b/2;
}
return r;
}
void solve(){
__int64 c=y/(x-1),g=gcd(c,a0);
if (c%a0==0){
printf("1n");
return;
}
a0/=g;
if (gcd(a0,x)>1){
printf("Impossible!n");
return;
}
__int64 times=phi(a0),ans=0x7FFFFFFF;
for (__int64 i=1;i<=times/i;i++)
if (times % i==0){
if (mod(x,i,a0)==1) ans=min(ans,i);
if (mod(x,times/i,a0)==1) ans=min(ans,times/i);
}
if (ans==0x7FFFFFFF) printf("Impossible!n");
else printf("%I64dn",ans);
}
int main(){
while (scanf("%I64d%I64d%I64d",&x,&y,&a0)!=EOF){
solve();
}
return 0;
}