上海建设电动车官方网站,投资加盟项目,python网站开发学习,如何设计一个好网站3792 质数问题
用的埃氏筛法#xff0c;st数组保存是否被筛掉#xff0c;遍历到的st为0的节点就是质数#xff0c;将其保存。
然后遍历所有相邻的节点得到判断是否存在条件中的质数。
#includebits/stdc.h
using namespace std;
//3792 质数问题
const int N1010…3792 质数问题
用的埃氏筛法st数组保存是否被筛掉遍历到的st为0的节点就是质数将其保存。
然后遍历所有相邻的节点得到判断是否存在条件中的质数。
#includebits/stdc.h
using namespace std;
//3792 质数问题
const int N1010;
vectorinta;//保存所有质数
int st[N];
int main()
{int n,k,t;cint;while(t--){memset(st,0,sizeof(st));a.clear();cinnk;for(int i2; in; i){if(!st[i]){a.push_back(i);//保存质数for(int jii; jn; ji)st[j]1;}}int cnt0;for(int i0; ia.size(); i){if(find(a.begin(),a.end(),a[i]a[i1]1)!a.end()){cnt;}}//coutcnt有endl;if(cntk)coutYESendl;else{coutNOendl;}}}868. 筛质数(线性筛质数)
线性筛法
#includebits/stdc.h
using namespace std;
//868 筛质数
const int N1e610;
int prime[N];//记录所有的质数
int st[N];//是否被筛掉
int idx0;
int n;
int main()
{cinn;for(int i2;in;i){if(!st[i])prime[idx]i;for(int j0;jidx;j){st[prime[j]*i]1;//被筛掉了if(i%prime[j]0){break;}}}coutidxendl;
}
4309 消灭老鼠
也就是消除所有的点需要几个不同的斜率。
记录每个斜率的分子分母的最大公约数除以这个数之后每个斜率的分子分母就是唯一的。之后再出现这个点在这个斜率上每次出现新的斜率就加加。
0和10的最大公约数是10。
解决了分母是0的情况。
#includebits/stdc.h
using namespace std;
//4309 消灭老鼠
typedef pairint,intPII;
mapPII,intmp;//保存某个斜率是否被保存过
//求最大公约数
int gcd(int a,int b)
{return b0?a:gcd(b,a%b);
}
int main()
{int n,x0,y0;cinnx0y0;int cnt0;while(n--){int a,b;cinab;int x(a-x0);int y(b-y0);int maxxgcd(x,y);x/maxx;y/maxx;PII t{x,y};if(mp[t]!5){mp[t]5;cnt;}}coutcntendl;
}872. 最大公约数
模板题
#includebits/stdc.h
using namespace std;
//872 最大公约数
int gcd(int a,int b)
{return b0?a:gcd(b,a%b);
}
int main()
{int n;cinn;while(n--){int a,b;cinab;coutgcd(a,b)endl;}
}200 Hankson的趣味题
Segmentation Fault
是线性筛、分解质因数、欧几里得的结合。
#includebits/stdc.h
using namespace std;
typedef pairint,intPII;
typedef long long LL;
const int N45000,M50;
vectorPIIa;//质因子和次数
int st[N];
int idx0;//约数下标
int idx20;//质数下标
int yue[N];//保存所有约数
int cntz0;//有几个质因子
int prime[N];//所有素数
//最大公约数
int gcd(int a,int b)
{return b0?a:gcd(b,a%b);
}
//求所有的质数
void getprim(int n)
{for(int i2;in;i){if(!st[i]){prime[idx2]i;}for(int j0;prime[j]n/i;j){st[prime[j]*i]1;if(i%prime[j]0)break;}}
}
//分解质因数
void fenjie(int n)
{//遇到一个数就将其榨干for(int i0;prime[i]n/prime[i];i){int cnt0;if(n%prime[i]0){while(n%prime[i]0){cnt;n/prime[i];}}a.push_back({prime[i],cnt});cntz;}if(n1)a.push_back({n,1}),cntz;;}void dfs(int n,int m)
{if(ncntz){yue[idx]m;return;}else{//遍历某个质数的所有可能性int numofita[n].second;int numa[n].first;for(int i0;inumofit;i){dfs(n1,m);m*num;}}
}
int main()
{int n;cinn;while(n--){int a0,a1,b0,b1;//要找的x一定是b1的因数。//找到所有b1的因数//然后满足题目要求的条件cina0a1b0b1;idx0;//约数下标idx20;memset(yue,0,sizeof(yue));memset(prime,0,sizeof(prime));memset(st,0,sizeof(st));a.clear();cntz0;//有几个质因子getprim(b1);
// for(int i0;iidx2;i)
// {
// coutprime[i] ;
// }
// cout以上为素数endl;if(idx2)fenjie(b1);
// for(int i0;icntz;i)
// {
// couta[i].first a[i].secondendl;
// }// cout以上为分解质因数endl;dfs(0,1);
// for(int i0;iidx;i)
// {
// coutyue[i] ;
// }
// cout以上为因数endl;int ans0;for(int i0;iidx;i){int xyue[i];if(gcd(x,a0)a1(LL)(x*b0)/gcd(x,b0)b1){ans;//coutxendl;}}coutansendl;}}
