问一下下,就是有一道题解通道已经关闭道题目,但是我有一个不毒瘤,个人感觉也不错,同时在已有题解里未出现的方法并且已经AC,然后想要分享这个做法,这种情况可以管理员们特殊处理嘛[可怜]
by TaK_Vin @ 2021-10-27 15:35:21
刚开始可以直接想到暴力
思路1:枚举公差和质数,幸灾乐祸的我只拿到了78分
代码如下:
```
#include<bits/stdc++.h>
using namespace std;
int a[10000001],f[10000001],index1,n,m,flag;
bool F=false;
int main()
{
memset(a,0,sizeof(a));
cin>>n>>m;
for(int i=0;i<=m;i++)
{
for(int j=0;j<=i;j++)
{
a[i*i+j*j]=true;
}
}
index1=0;
for(int j=1;j*n<=m*m*2;j++)
{
for(int i=0;i+n*j<=m*m*2;i++)
{
int k=0;
while(1)
{
int x=i+j*k;
if(x>m*m*2)break;
if(!a[x])break;
k++;
if(k==n){
cout<<i<<" "<<j<<endl;
F=true;
break;
}
}
}
}
if(!F)cout<<"NONE";
return 0;
}
```
要如何优化这种方法呢?首先想到筛数,接下来下讲一种线性筛数法(欧拉筛):
先从埃及筛数来:
埃氏筛法的基本思想 :从2开始,将每个质数的倍数都标记成合数,以达到筛选素数的目的。
```
int visit[maxn];
void Prime(){
mem(visit,0); //初始化都是素数
visit[0] = visit[1] = 1; //0 和 1不是素数
for (int i = 2; i <= maxn; i++) {
if (!visit[i]) { //如果i是素数,让i的所有倍数都不是素数
for (int j = i*i; j <= maxn; j += i) {
visit[j] = 1;
}
}
}
```
欧拉筛法的基本思想 :在埃氏筛法的基础上,让每个合数只被它的最小质因子筛选一次,以达到不重复的目的
```
int prime[maxn];
int visit[maxn];
void Prime(){
mem(visit,0);
mem(prime, 0);
for (int i = 2;i <= maxn; i++) {
cout<<" i = "<<i<<endl;
if (!visit[i]) {
prime[++prime[0]] = i; //纪录素数, 这个prime[0] 相当于 cnt,用来计数
}
for (int j = 1; j <=prime[0] && i*prime[j] <= maxn; j++) {
// cout<<" j = "<<j<<" prime["<<j<<"]"<<" = "<<prime[j]<<" i*prime[j] = "<<i*prime[j]<<endl;
visit[i*prime[j]] = 1;
if (i % prime[j] == 0) {
break;
}
}
}
}
```
又惹我能说这跟素数有什么关系吗,确实没关系,但我们可以用同样的方法,用一个数组来标记。
代码如下:
```
#include<bits/stdc++.h>
using namespace std;
int a[10000001],f[10000001],index1,n,m,flag;
bool F=false;
int main()
{
memset(a,0,sizeof(a));
cin>>n>>m;
for(int i=0;i<=m;i++)
{
for(int j=0;j<=i;j++)
{
a[i*i+j*j]=true;
}
}
index1=0;
for(int j=1;j*(n-1)<=m*m*2;j++)
{
for(int i=0;i+(n-1)*j<=m*m*2;i++)
{
int k=0;
while(1)
{
int x=i+j*k;
if(x>m*m*2)break;
if(!a[x])break;
k++;
if(k==n){
cout<<i<<" "<<j<<endl;
F=true;
break;
}
}
}
}
if(!F)cout<<"NONE";
return 0;
}
```
很明显,洛谷上的节点有点弱,我自己编了一组数据,第一串只有55分,第二串只有77分,如何提高呢,思路3:找数中的a和b(a<b),a为首项,b-a为公差
代码如下:
```
#include<bits/stdc++.h>
using namespace std;
struct point{
int cnt,res;
};
point ans[10010];
int n,m,cnt,tot;
bool vis[250*250*2+10];
bool cmp(point x,point y){
if(x.res<y.res)return true;
if(x.res==y.res&&x.cnt<y.cnt)return true;
return false;
}
int main(){
cin>>n>>m;
for(int i=0;i<=m;i++)
for(int j=0;j<=m;j++)
vis[i*i+j*j]=true;
int maxm=m*m*2;
for(int i=0;i<=maxm;i++)
if(vis[i])
for(int j=i+1;j<=maxm;j++)
if(vis[j]){
int d=j-i;
int maxi=i+d*(n-1);
if(maxi>maxm)break;
bool f=true;
for(int j=i+d;j<=maxi;j+=d)
if(!vis[j]){
f=false;
break;
}
if(f){
tot++;
ans[tot].cnt=i;
ans[tot].res=d;
}
}
if(tot==0){
cout<<"NONE";
return 0;
}
sort(ans+1,ans+tot+1,cmp);
for(int i=1;i<=tot;i++)
cout<<ans[i].cnt<<' '<<ans[i].res<<endl;
return 0;
}
```
这样就能AC自己的数据节点了
其实刚开始就有点带跑偏了
我们可以用一些数学性质来完成
by kanroji @ 2021-10-30 14:02:29
请问数据类型(如 int)是否需要 $\LaTeX$?是该写成下面哪种形式?
- int
- $int$
- $\operatorname{int}$
即
```
int
$int$
$\text{int}$
by Fishmaster @ 2021-10-30 14:54:51
大佬,怎么发布题解?
by songziyu @ 2021-10-31 10:58:38
@[songziyu](/user/543078) 题解界面左上角如果有按钮 $"提交题解"$ 就可以按进去写题解
by william_zy @ 2021-11-01 21:56:05
OK
by Somebady @ 2021-11-04 17:54:36
点提交,为什么不显示待提交啊?~~
by 淡泊芝士 @ 2021-11-05 17:34:08
请问太长的代码可以直接放剪切板上贴链接吗?谢谢了!
by amlelephant @ 2021-11-05 22:19:23
@[chen_zhe](/user/8457) 你好。
请问如果我提交了一篇题解,但没有审核通过,这时候我把这篇题解修改了一下,再次提交,会通过我那次的提交申请(如果会通过的话)。
谢谢。
by Aphasia_Ray @ 2021-11-06 20:32:08
@[william_zy](/user/201971) 谢谢
by songziyu @ 2021-11-07 08:45:43