Codeforces Round #324 (Div. 2) （快速判断素数模板）

提示：扫一扫查出行
【扫一扫了解最新限行尾号】
复制提示

蛋疼的比赛，当天忘了做了，做的模拟，太久没怎么做题了，然后C题这么简单的思路却一直卡到死，期间看了下D然后随便猜了下，暴力了下就过了。

A.找一个能被t整除的n位数，那么除了<=10以外，其他都可以用长度为n的10或100,1000 。。。来往上加几个数而得到

#include <iostream>
#include <stdio.h>
#include <set>
#include <algorithm>
#include <string.h>
using namespace std;int getwei(int x)
{
int sum=;
while(x)
{
sum++;
x=x/;
}
return sum;
}
int main()
{
int n,t;
scanf("%d%d",&n,&t);
if(n==&&t==)
printf("-1");
else if(n==)
{
printf("%d",t);
}
else
{
int save;
for(int i=;i<;i++)
{
if(i%t==)
{
save=i;
break;
}
}
printf("%d",save);
for(int i=;i<n;i++)
{
printf("");
}
}
return ;
}

B.很好找的公式题，((27^n-7^n)%MOD+MOD)%MOD。n很不大所以直接暴力就行了。

#include <iostream>
#include <stdio.h>
#include <set>
#include <algorithm>
#include <string.h>
using namespace std;
#define MOD 1000000007int main()
{
int n;
scanf("%d",&n);
long long tmp=;
long long tmp1=;
for(int i=;i<n;i++)
{
tmp=tmp*;
tmp%=MOD;
tmp1=tmp1*;
tmp1%=MOD;
}
tmp-=tmp1;
tmp= (tmp%MOD+MOD)%MOD;
cout<<tmp<<endl;
return ;
}

C.思维题，给出了长度为n的两个字符串a和b，要你找到一个c串使得c串分别与a串和b串的相同位置不同字符数恰好为t。可以这样想，如果在某个位置i上

如果a[i]==b[i]，那么可以贡献a和b相异值1或0

如果a[i]!=b[i],那么要么贡献串a的相异值为1，要么贡献b的相异值为1，要么同时贡献a和b的相异值1.

因为ab的相异值必须得相等，那么最小的相异值为：所有a[i]!=b[i]的个数和为sumaneb，(sumaneb+1)/2 。如果这个值>t那么必定无解，否则一定有解。

如果有解，因为a[i]==b[i]的情况是可控的，所以尽量先把这种情况全部加进来，如果这种情况全部算进来却还是小于t，那么就将a[i]!=b[i]的情况变成对a和b同时贡献的情况。

这样想其实挺复杂的，判断情况就要想，还得推公式一种情况弄个c串。

看了大神的代码立马觉得涨姿势，果真自己的思路太弱。大神的做法是先得出一个c串，使得和ab串完全不相等。然后从a[i]==b[i]的情况中一个一个加入相等的情况，如果全部设为相等后还是不够，那就冲a[i]!=b[i]中加入相等的，如果全部加完还是不行就输出-1.

用这种思路的大神开场不到20分钟就把这题A了。。。

#include <iostream>using namespace std;int n, t;
string a;
string b;
string c;int main() {
cin >> n >> t;
cin >> a >> b;
int u = n;
c = a;
for (int i = ; i < n; i++) {
char x = 'a';
if (a[i] == x || b[i] == x) x = 'b';
if (a[i] == x || b[i] == x) x = 'c';
c[i] = x;
}
for (int i = ; i < n; i++) {
if (a[i] == b[i] && t != u) {
c[i] = a[i];
u--;
}
}
int z = ;
for (int i = ; i < n; i++) {
if (a[i] == b[i] || u == t) continue;
if (z == ) {c[i] = a[i]; z = ;}
else {c[i] = b[i]; u--; z = ;}
}
if (u == t) cout << c << "\n";
else cout << "-1\n";
}

D.给出一个3到10^9的整数n，然后要求输出三个素数a,b,c使得a+b+c=n.

哥德巴赫猜想：任何一个大于二的偶数都可以分解为两个素数和。

我的猜想是任意一个<=10^9的偶数，都可以快速分拆为两个素数和。所以就可以将n-3快速拆分为两个素数。

其实我这种猜想风险还太大，我使用了rabbin算法快速的判断一个数是不是素数，但是这种方法虽然快但不是绝对正确的，有一定的失误率。

#include <iostream>
#include <algorithm>
#include <string.h>
#include <stdio.h>
using namespace std;#define S 100
typedef unsigned long long LL;LL modular_multi(LL x,LL y,LL mo)
{
LL t;
x%=mo;
for(t=;y;x=(x<<)%mo,y>>=)
if (y&)
t=(t+x)%mo;
return t;
}LL modular_exp(LL num,LL t,LL mo)
{
LL ret=,temp=num%mo;
for(;t;t>>=,temp=modular_multi(temp,temp,mo))
if (t&)
ret=modular_multi(ret,temp,mo);
return ret;
}bool miller_rabbin(LL n)
{
if (n==)return true;
if (n<||!(n&))return false;
int t=;
LL a,x,y,u=n-;
while((u&)==) t++,u>>=;
for(int i=;i<S;i++)
{
a=rand()%(n-)+;
x=modular_exp(a,u,n);
for(int j=;j<t;j++)
{
y=modular_multi(x,x,n);
if (y==&&x!=&&x!=n-)
return false;
///其中用到定理，如果对模n存在1的非平凡平方根，则n是合数。
///如果一个数x满足方程x^2≡1 (mod n),但x不等于对模n来说1的两个‘平凡’平方根：1或-1，则x是对模n来说1的非平凡平方根
x=y;
}
if (x!=)///根据费马小定理,若n是素数，有a^(n-1)≡1(mod n).因此n不可能是素数
return false;
}
return true;
}
int main()
{
int n;
scanf("%d",&n);
if(n==) printf("1\n3");
else if(n==)
printf("2\n2 3");
else
{
n-=;
for(int i=;i<=n;i++)
{
if( miller_rabbin(i) ==true)
{
if(miller_rabbin(n-i) == true)
{
printf("3\n3 %d %d",i,n-i);
break;
}
}
}
}
return ;
}

我乱搞的算法

更确定的算法是，从n->1，先求出一个素数复杂度约等于10*sqrt(n)，然后剩下来的就暴力几乎不要时间。

E.这题想了挺久的。

其实问题可以简化为

1 2 3 4 ... n

a1 a2 a3 a4 .. an

标号为ai的要到i位置。然后每次交换为|i-j|费用，ij为标号。

我的思路是既然现在交换是看之间相隔的距离了，那么我把一个长的交换分拆成小的交换可以换的更好的效果。具体做法是：

对于没一个ai，如果ai>i,这ai这个数需要往右移，将这个位置标记为>

如果ai<i,这ai这个数需要往左移，将这个位置标记为<

如果ai=i,这ai这个数已经到达位置，将这个位置标记为0

比如一组数据

1 2 3 4 5

3 4 5 1 2

就可以变为

1 2 3 4 5

> > > < <

接着对于没一个相邻或者中间只隔0的><的情况进行变换，知道所有的状态都为0

比如

3 4 5 1 2 （>>><<）->

3 4 1 5 2 (>><><)->

3 1 4 5 2 (><>><)->

1 3 4 5 2 (0>>><)->

1 3 4 2 5 (0>><0)->

1 3 2 4 5 (0><00)->

1 2 3 4 5 (00000)结束。

#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <algorithm>
#include <string.h>
#include <math.h>
using namespace std;
#define N 2020int f[N],tf[N];
int mylink[N];
int g[N];
int x[N*N],y[N*N];
int cnt;int main()
{
int ans=;
int n;
scanf("%d",&n);
for(int i=;i<=n;i++)
{
scanf("%d",tf+i);
}
for(int i=;i<=n;i++)
{
scanf("%d",f+i);
mylink[f[i]]=i;
}
for(int i=;i<=n;i++)
{
tf[i]=mylink[ tf[i] ];
}
for(int i=;i<=n;i++)
{
if(tf[i]==i) g[i]=;
else if(tf[i]>i) g[i]=;
else g[i]=-;
}
while()
{
int flag=;
int pre=-;
int id=-;
for(int i=;i<=n;i++)
{
if(g[i]==-)
{
if(pre==)
{
swap(tf[id],tf[i]);
if(tf[id]>id) g[id]=;
else if(tf[id]==id) g[id]=;
else g[id]=-; if(tf[i]>i) g[i]=;
else if(tf[i]==i) g[i]=;
else g[i]=-;
flag=;
x[cnt]=id;
y[cnt]=i;
ans+=i-id;
cnt++;
if(tf[i]==i) break;
else
{
pre=;
id=i;
}
}
else
pre=-;
}
else if(g[i]==)
{
pre=;
id=i;
}
}
if(flag==) break;
}
printf("%d\n",ans);
printf("%d\n",cnt);
for(int i=;i<cnt;i++)
printf("%d %d\n",x[i],y[i]);
return ;
}