CodeforcesRound#257(Div.2)E（数论+构造）
作者：脉趣小鱼 | 来源：互联网 | 2023-05-17 17:29
E.JzzhuandApplestimelimitpertest1second
Jzzhu has picked n apples from his big apple tree. All the apples are numbered from 1 to n. Now he wants to sell them to an apple store.
Jzzhu will pack his apples into groups and then sell them. Each group must contain two apples, and the greatest common divisor of numbers of the apples in each group must be greater than 1. Of course, each apple can be part of at most one group.
Jzzhu wonders how to get the maximum possible number of groups. Can you help him?
Output
The first line must contain a single integer m, representing the maximum number of groups he can get. Each of the next m lines must contain two integers — the numbers of apples in the current group.
If there are several optimal answers you can print any of them.
题意：在1到n的数中，找出尽量多的数对，使得每对数的最大公约数>1
思路：先看 1 和大于 n / 2 的素数，这些数可以直接删掉，因为它们不可能和其它任何数配对
然后对于所有素数 x 且 2 < x <= n / 2，在剩下的未选的数中找出 x 的倍数，看这些数的数量是否为偶数，为偶数可以直接两两配对，如果为奇数，则忽略 x*2，将剩下的
数两两配对
最后只剩下2的倍数的数没有被配对，两两配对即可
#include
#include
#include
#include
#include
using namespace std;
typedef long long ll;
int n;
int d;
int top;
int isprime[100010];
int prime[10010];
int ansx[100010];
int ansy[100010];
int vis[100010];
int stk[100010];
void getprime()
{
d=0;
for(ll i=2;i<=50000;i++)if(!isprime[i])
{
prime[d++]=i;
for(ll j=i*i;j<=100000;j+=i)isprime[j]=1;
}
}
int main()
{
getprime();
while(scanf("%d",&n)!=EOF)
{
int i,j;
int dd=0;
int aa=0;
memset(vis,0,sizeof(vis));
for(i=1;prime[i]<=n/2&&i
![[大整数乘法] java代码实现](https://img1.php1.cn/3cd4a/24c6f/9f3/0133bb25da242824.jpeg)
京公网安备 11010802041100号 | 京ICP备19059560号-4 | PHP1.CN 第一PHP社区 版权所有