取模(mod)
【题目描述】
有一个整数a和n个整数b_1, …, b_n。在这些数中选出若干个数并重新排列，得到c_1,…, c_r。我们想保证a mod c_1 mod c_2 mod … mod c_r=0。请你得出最小的r，也就是最少要选择多少个数字。如果无解，请输出-1.
【输入说明】
输入文件的第一行有一个正整数T，表示数据组数。
接下去有T组数据，每组数据的第一行有两个正整数n和a.
第二行有n个正整数b_1, …, b_n.
【输出说明】
一行，输出答案。
【样例输入】
2
2 9
2 7
2 9
6 7
【样例输出】
2
-1
【数据范围】
对于40%的数据,n<=8
对于100%的数据,T<=5,n<=20,1 <=a <=10^6,b_i<=10^6
/*
因为先模小数再模大数是没有意义的，所以要从大到小排序，然后直接搜索。
*/
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define inf 10000000
using namespace std;
int T,x,n,ans;
int a[];
int init()
{
int x=,f=;char c=getchar();
while(c<''||c>''){if(c=='-')f=-;c=getchar();}
while(c>=''&&c<=''){x=x*+c-'';c=getchar();}
return x*f;
}
void dfs(int w,int t,int now)
{
if(t>=ans)return;
if(now==){ans=t;return;}
if(w==n+)return;
dfs(w+,t,now);
dfs(w+,t+,now%a[w]);
}
int cmp(int a,int b)
{
return a>b;
}
int main()
{
freopen("mod.in","r",stdin);
freopen("mod.out","w",stdout);
T=init();
while(T--)
{
n=init();x=init();
for(int i=;i<=n;i++)
a[i]=init();
sort(a+,a+n+,cmp);
ans=inf;
dfs(,,x);
if(ans==inf) printf("-1\n");
else printf("%d\n",ans);
}
fclose(stdin);fclose(stdout);
return ;
}
【题目描述】
判断一个数列是否为等比数列。
等比数列的定义为能被表示成a,aq,aq^2,aq^3...的数列，其中a和q不等于0。
【输入说明】
输入文件的第一行有一个正整数T，表示数据组数。
接下去有T组数据，每组数据的第一行一个整数n，接下来第二行n个数非负整数Ai，表示数列。
【输出说明】
对于每一个组的每个数据输出单独一行Yes或者No。
【样例输入】
2
3
1 1 1
3
1 4 2
【样例输出】
Yes
No
【数据范围】
对于40%的数据 0<=Ai<=10^9
对于100％的数据 T<=5,n<=1000,0<=Ai<=10^100
/*利用等比中项+高精乘法判断*/
#include<iostream>
#include<cstdio>
#include<cstring>
#define N 1010
#define M 310
using namespace std;
int T,n;
int t[M],r[M];
int a[N][M];
char s[M];
int init()
{
int x=,f=;char c=getchar();
while(c<''||c>''){if(c=='-')f=-;c=getchar();}
while(c>=''&&c<=''){x=x*+c-'';c=getchar();}
return x*f;
}
void mul(int c[M],int a[M],int b[M])
{
int l1=a[],l2=b[];
for(int i=;i<=l1;i++)
{
int x=;
for(int j=;j<=l2;j++)
{
c[i+j-]+=a[i]*b[j]+x;
x=c[i+j-]/;
c[i+j-]%=;
}
c[i+l2]+=x;
}
c[]=l1+l2;
while(c[]>&&c[c[]]==)c[]--;
}
int judge(int a[M],int b[M])
{
int l1=a[],l2=b[];
if(l1!=l2)return ;
for(int i=;i<=l1;i++)
if(a[i]!=b[i])return ;
return ;
}
int main()
{
freopen("sequence.in","r",stdin);
freopen("sequence.out","w",stdout);
T=init();
while(T--)
{
n=init();
memset(a,,sizeof(a));
for(int i=;i<=n;i++)
{
scanf("%s",s);
int l=strlen(s);a[i][]=l;
for(int j=;j<=l;j++)
a[i][j]=s[l-j]-'';
}
if(a[][]==&&a[][]==)
{
printf("No\n");
continue;
}
if(n==)
{
printf("Yes\n");
continue;
}
if(a[][]==&&a[][]==)
{
printf("No\n");
continue;
}
if(n==)
{
printf("Yes\n");
continue;
}
int flag=;
for(int i=;i<=n;i++)
{
memset(t,,sizeof(t));
mul(t,a[i-],a[i]);
memset(r,,sizeof(r));
mul(r,a[i-],a[i-]);
if(judge(t,r))continue;
flag=;break;
}
if(flag)
{
printf("No\n");
continue;
}
printf("Yes\n");
}
fclose(stdin);fclose(stdout);
return ;
}
回文串(palindromes)
【题目描述】
判断是否能将字符串S分成三段非空回文串。
【输入说明】
第一行一个整数T，表示数据组数。
对于每一个组，仅包含一个由小写字母组成的串。
【输出说明】
对于每一组，单行输出"Yes" 或 "No"。
【样例输入】
2
abc
abaadada
【样例输出】
Yes
No
【数据范围】
对于40%的数据，|S|<=100
对于60%的数据，|S|<=1000
对于100%的数据，T<=20，|S|<=20000