D - Two Divisors (素数筛)

「爱情、让人受尽委屈。」 2021-07-16 11:42 374阅读 0赞

[题目][Link 1]

首先：对于gcd有  
gcd(a,b)=gcd(a+b,b)  
且若gcd(a,b)=1,  
则gcd(a,c)=gcd(a,c\*b)=gcd(a,c \* b^n)  
现有gcd(d1,d2)=1,->gcd(d1+d2,d1)=1,gcd(d1+d2,d2)=1  
\->gcd(d1+d2,d1 \* d2)=1,->gcd(d1+d2,d1^n \* d2^n)

现在再来看题目要我们求什么，我们只需找到ai的两个互质因数d1,d2 , ai=d1^ n \* d2可得gcd(d1,d2)=1,由如上性质gcd(d1+d2，d1^n\*d2)=1,即gcd(d1+d2,ai)=1。

在此我们用埃拉托色尼筛法在 O(NloglogN)求出1e7内每个数的第一个质因数d1，第二个与d1互质因数只需用ai当ai%d1==0时不断除d1即可求出，如果最终d2=1表示找不到两个互质因数，反则可以。

Code:

#include<iostream>
    using namespace std;
    typedef long long ll;
    const int Max = 5e5 + 5;
    int prim[Max*20], vis[Max*20], h[Max*20], x = 0;//h存储合数找到的第一个质因数
    int a[Max], b[Max];
    void eratos(int n)
    { 
    	for (int i = 2;i <= n;i++)
    	{ 
    		if (!vis[i])prim[++x] = i;
    		if (vis[i])continue;
    		for (int j = 1;j * i <= n;j++)
    		{ 
    			if(j!=1)vis[i * j] = 1;
    			h[i * j] = i;
    		}
    	}
    }
    
    int main()
    { 
    	int n;cin >> n;
    	eratos(1e7+3);
    	for (int i = 1;i <= n;i++)
    	{ 
    		int p;cin >> p;
    		if (vis[p] == 0)a[i] = -1, b[i] = -1;
    		else
    		{ 
    			int k = h[p];
    			while (p % k == 0)p /= k;
    			if (p == 1)a[i] = -1, b[i] = -1;
    			else a[i] = k, b[i] = p;
    		}
    	}
    	for (int i = 1;i <= n;i++)cout << a[i] << " ";cout << endl;
    	for (int i = 1;i <= n;i++)cout << b[i] << " ";
    }

[Link 1]: https://codeforces.ml/contest/1366/my

发表评论取消回复

表情：

评论列表（有 0 条评论，374人围观）

还没有评论，来说两句吧...

相关阅读

相关素数筛

目录题目思路1 思路2 思路3 题目给定一个正整数n(2≤n≤10000)，先输出2~n之间的素数个数

拼搏现实的明天。/ 2023年10月06日 16:35/ 0 赞/ 47 阅读

相关 POJ 2689【筛法求素数+区间筛素数】

Discription The branch of mathematics called number theory is about properties of numb

桃扇骨/ 2023年07月04日 06:15/ 0 赞/ 19 阅读

相关素数筛模板

查找N内所有素数 1.埃氏筛 include<iostream> using namespace std; typede

约定不等于承诺〃/ 2022年11月06日 00:59/ 0 赞/ 155 阅读

相关素数筛法略

用筛法求素数的基本原理，是把从1开始的某一范围内的正整数从小到大顺序排列，逐步筛掉非素数留下素数。用筛法求素数的基本思想是：把从1开始的、某一范围内的正整数从小到大顺序排列

墨蓝/ 2022年10月25日 01:23/ 0 赞/ 179 阅读

相关筛法求素数

用筛法求素数的基本思想是：把从1开始的、某一范围内的正整数从小到大顺序排列， 1不是素数，首先把它筛掉。剩下的数中选择最小的数是素数，然后去掉它的倍数。依次类推，直到筛子为空时

我不是女神ヾ/ 2022年05月12日 14:42/ 0 赞/ 258 阅读

相关素数筛法

//暴力枚举素数筛法 o(n 根号n) for(int i=2;i<=n;i++){ bool g=0; for(int j=2;jj<

╰+哭是因爲堅強的太久メ/ 2022年04月04日 10:54/ 0 赞/ 253 阅读

相关素数筛C++

埃拉托斯特尼筛法（sieve of Eratosthenes ）是古希腊数学家埃拉托斯特尼发明的计算素数的方法。对于求解不大于n的所有素数，我们先找出sqrt(n)内的所有素

向右看齐/ 2022年02月09日 11:15/ 0 赞/ 270 阅读

相关数论2：素数筛

埃氏筛判断素数可通过试除小于\\(\\sqrt n\\)的素数来实现，那么将其反过来，只要将\\(<= \\sqrt n\\)的素数的倍数都删掉，那么就能得到一张\\(

向右看齐/ 2021年09月20日 11:56/ 0 赞/ 369 阅读

相关 D - Two Divisors (素数筛)

[题目][Link 1] 首先：对于gcd有 gcd(a,b)=gcd(a+b,b) 且若gcd(a,b)=1, 则gcd(a,c)=gcd(a,c\b

「爱情、让人受尽委屈。」/ 2021年07月16日 11:42/ 0 赞/ 375 阅读

相关筛法判断素数

1.埃氏筛选法 include <iostream> include <algorithm> using namespace std; con

ゝ一纸荒年。/ 2021年06月22日 15:37/ 0 赞/ 442 阅读