商城网站设计价格,django和WordPress哪个好,wordpress 导航栏在哪里,wordpress建立扁平化题目大意#xff1a;把1到n分为不互质的数对#xff0c;找最多的对数
思路#xff1a;先从最大的质因数开始找#xff0c;因为小的比大的更容易匹配#xff0c;所以贪心的从大的开始找。 首先要预处理出所以数的最大质因数。 然后根据质因数从大往小找#xff0c;当质因… 题目大意把1到n分为不互质的数对找最多的对数
思路先从最大的质因数开始找因为小的比大的更容易匹配所以贪心的从大的开始找。 首先要预处理出所以数的最大质因数。 然后根据质因数从大往小找当质因数大于n/2的时候 就找不到 配对了。 估计是偶数 直接配对如果是奇数 讲2*p留出来这样留到最后这些数必定有2的公因子。 代码:
#include cstdio
#include cstring
#include string
#include cmath
#include iostream
#include algorithm
#include queue
#include cstdlib
#include stack
#include vector
#include set
#include map
#include bitset
#define INF 0x3f3f3f3f3f3f3f3f
#define inf 0x3f3f3f3f
#define FILL(a,b) (memset(a,b,sizeof(a)))
#define re register
#define lson rt1
#define rson rt1|1
#define lowbit(a) ((a)-(a))
#define ios std::ios::sync_with_stdio(false);std::cin.tie(0);std::cout.tie(0);
#define fi first
#define rep(i,n) for(int i0;(i)(n);i)
#define rep1(i,n) for(int i1;(i)(n);i)
#define se secondusing namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pairint,int pii;
const ll mod1e97;
const ll N 2e510;
const double eps 1e-4;
const double piacos(-1);
int gcd(int a,int b){return !b?a:gcd(b,a%b);}int x[4] {-1,0,1,0}, dy[4] {0,1,0,-1};
int st[N];vectorint p[N];
int c[N];
int mx[N];
int r[N];
int idx0;
int k[N];
int id;
void get_primes(int n)
{st[1]1;for (int i 2; i n; i ){if (!st[i]){mx[i]i;for(int jii;jn;ji){st[j]1;mx[j]i;}}}
}void solve()
{idx0;int n;cinn;for(int i2;in;i){if(!st[i]2*in) continue;p[mx[i]].push_back(i);}vectorpii a;for(int in;i2;--i){int lep[i].size();if(le%21){id0;r[idx]i*2;for(int j0;jle;j) if(p[i][j]!2*i) k[id]p[i][j];for(int j0;jid;j2) a.push_back({k[j],k[j1]});}else{for(int j0;jle;j2) a.push_back({p[i][j],p[i][j1]});}}for(int i0;i1idx;i2) a.push_back({r[i],r[i1]});couta.size()endl;for(pii v:a){coutv.fi v.seendl;}for(int i1;in;i) p[i].clear();
}int main()
{iosint T;cinT;get_primes(N);//T1;while(T--){solve();}return 0;
}
