admin管理员组文章数量:1594646
Interesting Numbers
URAL - 2070
Nikolay and Asya investigate integers together in their spare time. Nikolay thinks an integer is interesting if it is a prime number. However, Asya thinks an integer is interesting if the amount of its positive divisors is a prime number (e.g., number 1 has one divisor and number 10 has four divisors).
Nikolay and Asya are happy when their tastes about some integer are common. On the other hand, they are really upset when their tastes differ. They call an integer satisfying if they both consider or do not consider this integer to be interesting. Nikolay and Asya are going to investigate numbers from segment [ L; R] this weekend. So they ask you to calculate the number of satisfying integers from this segment.
Input
In the only line there are two integers L and R (2 ≤ L ≤ R ≤ 10 12).
Output
In the only line output one integer — the number of satisfying integers from segment [ L; R].
Example
input | output |
---|---|
3 7 | 4 |
2 2 | 1 |
77 1010 | 924 |
思路:把不符合的减去就行了
#include <algorithm>
#include <iostream>
#include <cstring>
#include <vector>
#include <string>
#include <functional>
#include <cstdio>
#include <cmath>
#include <list>
#include <set>
#include <map>
#include <queue>
#include <stack>
using namespace std;
#define ll long long
#define F first
#define S second
#define p_b push_back
#define m_p make_pair
const ll LINF = 0x3f3f3f3f3f3f3f3f;
const int INF = 0x3f3f3f3f;
const int mod = 1e9 + 7;
const int M = 1e7 + 7;
const int N = 1e6 + 100;
ll prime[N];
int isprime[N];
void getprime() {
memset(prime, 0, sizeof(prime));
int n = 1e6+20;
for (int i = 2; i <= n; ++i) {
if (!prime[i]) prime[++prime[0]] = i, isprime[i] = 1;
for (int j = 1; j <= prime[0] && prime[j] <= n/i; ++j) {
prime[prime[j]*i] = 1;
if (i % prime[j] == 0) break;
}
}
}
ll sum(ll x) {
ll not_is = 0;
for (int i = 1; ; ++i) {
ll y = prime[i]*prime[i];
int num = 3;
if (y > x) break;
while (y <= x) {
if (isprime[num])
++not_is;
y *= prime[i];
++num;
}
}
return x - not_is;
}
int main() {
getprime();
//printf ("%d\n", prime[0]);
ll l, r;
scanf ("%lld %lld", &l, &r);
printf ("%lld\n", sum(r) - sum(l-1));
return 0;
}
本文标签: 规律NUMBERSInterestingURAL
版权声明:本文标题:Interesting Numbers URAL - 2070 (规律) 内容由热心网友自发贡献,该文观点仅代表作者本人, 转载请联系作者并注明出处:https://www.elefans.com/xitong/1728178990a1148211.html, 本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容,一经查实,本站将立刻删除。
发表评论