K. Lonely Numbers(线性筛 + 差分)_学习

K. Lonely Numbers(线性筛 + 差分)

创始人

2024-04-30 19:08:05

Problem - 1423K - Codeforces

在数字世界中，如果两个不同的数字有很多共同点，而且每个数字都有独特的好处，那么它们就是朋友。

更确切地说，如果gcd(a,b), agcd(a,b), bgcd(a,b)能组成一个三角形的边，那么两个不同的数字a和b就是朋友。

如果a+b>c，b+c>a，c+a>b，三个数字a，b，c可以组成一个三角形的边。

在一个数组中，如果一个数字在该组中没有任何朋友，那么这个数字就是孤独的。

给出一个包含1,2,3,...,n中所有数字的数组，该数组中有多少个数字是孤独的？

输入
第一行包含一个整数t（1≤t≤106）--测试案例的数量。

下一行有t个数字，ni (1≤ni≤106) - 意味着在案例i中你应该求出数字1,2,3,...,ni。

输出
对于每个测试案例，在不同的行上打印答案：1,2,3,...,ni组中孤独的数字数量。

例子
输入复制
3
1 5 10
outputCopy
1
3
3
注意
对于第一个测试案例，1是唯一的数字，因此是孤独的。

对于第二个测试案例，n=5，数字1，3和5是孤独的。

对于第三个测试案例，n=10，数字1，5和7是孤独的。

题解:

经过我们枚举一些例子,发现只要一个数是素数他一定是一个孤独的数,因为一个素数除了和他的平方,都无法符合题意,

假如n = 5

3肯定是一个孤独的数,他和其他数的gcd肯定是1,n <= 5除3的任何数都无法符合题意

因此我们线性筛求出范围内所有质数,然后质数++,质数平方位--

最后差分就是我们预处理除来的答案

#include
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;
#define int long long
typedef pair PII;
int p[1000060];
int vis[1000060];
int ans[1000050];
int cnt = 0;
void solve()
{for(int i = 2;i <= 1000000;i++){if(!vis[i])p[cnt++] = i;for(int j = 0;j < cnt&&i*p[j] <= 1000000;j++){vis[i*p[j]] = 1;if(i%p[j] == 0)break;}}ans[1] = 1;for(int i = 0;i < cnt;i++){if(p[i] <= 1000){ans[p[i]*p[i]]--;}ans[p[i]]++;}for(int i = 1;i <= 1000000;i++)ans[i] += ans[i-1];int t;cin >> t;while(t--){int n;cin >> n;cout << ans[n]<<"\n";}
}
//5 2
//
signed main()
{ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);int t = 1;
//	cin >> t;while(t--){solve();} 
}

上一篇：Python模块学习，模块是，什么

下一篇：初识Docker：（1）什么是docker

K. Lonely Numbers(线性筛 + 差分)

相关内容

热门资讯