ICPC2019徐州区域赛复现赛C < 3 numbersF. The Answer to the Ultimate Question of Life, The Universe, and Everything.Cat

51 阅读 0 评论 34 点赞

我是靠谱客的博主忧伤保温杯，最近开发中收集的这篇文章主要介绍ICPC2019徐州区域赛复现赛C < 3 numbersF. The Answer to the Ultimate Question of Life, The Universe, and Everything.Cat，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

C < 3 numbers

教训就是不能看见素数就不管三七二十一直接上线性筛板子，还是需要多仔细想想题意。

题解：
解法一
这是一道素数密度的题目，首先需要推出一个结论。一个常识就是素数越往后是越来越分散的。观察素数表以后可以发现从100左右开始，如果区间长度超过了50（估计值），那么区间内的素数一定小于1/3.。如果区间的长度小于50，那么对于这个区间内的所有数做一遍√n的素数判断就可以。

代码：

#include<bits/stdc++.h>
#define ll long long
#define inf 0x3f3f3f3f
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define endl 'n'
using namespace std;


int b[25] = {2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97};
const int N = 1e5 + 100;

bool prime(int x)
{
	for(int i = 0; i < 25; i ++)
	{
		if(x % b[i] == 0 && x != b[i])
			return 0;
	}
	return 1;
}

int main()
{
	int t;
	scanf("%d", &t);
	while(t --)
	{
		int l, r;
		scanf("%d%d", &l, &r);
		if(l == r)
		{
			if(l == 1 || prime(l) == 1) puts("No");
			else puts("Yes");
		}
		else if(r >= 100 && r - l > 50) puts("Yes");
		else
		{
			ll ans = 0;
			int bj = 0;
			int len = r - l + 1;
			for(int i = l; i <= r; i ++)
			{
				if(prime(i)) ans ++;
				if(ans * 3 >= len) 
				{
					puts("No");
					bj = 1;
					break;
				}
			}
			if(!bj) puts("Yes");
		}
	}
	return 0;
}

解法二
可以使用Robin-Miller 素数测试来判断素数,复杂度O(MAX log（n）)。

#include <bits/stdc++.h>
#define inf 0x3f3f3f3f
#define fi first
#define se second
#define endl 'n'
#define Sezuna 0
#define IOS std::ios::sync_with_stdio(false),cin.tie(0), cout.tie(0)
using namespace std;

typedef long long ll;
const ll INF = 0x3f3f3f3f3f3f3f3f;
const int N = 1e6 + 100;

 
long long PowerMod(long long a, long long b, long long k) 
{
    long long ret = 1, f = a;
 
    while (b) {
        if (b & 1)
            ret = ret * f % k;
        f = f * f % k;
        b >>= 1;
    }
    return ret;
}

bool MillerRobin(long long n,int MAX) 
{
    int i;
    long long tmp;
 
    srand(100);
    for (i = 0; i < MAX; i++) {
        tmp = rand() % (n - 1) + 1;
        if (PowerMod(tmp, n - 1, n) != 1)
            break;
    }
    return (i == MAX);
}

int main()
{
	int t;
	scanf("%d", &t);
	while(t --)
	{
		int bj = 0;
		ll l, r;
		ll ans = 0;
		scanf("%lld%lld", &l, &r);
        ll len = r - l + 1;
        if(l == r)
        {
            if(l == 1 || MillerRobin(l, 50) == 1) puts("No");
            else puts("Yes");
        }
        else if(r >= 100 && len > 100) puts("Yes");
        else
        {
            if(l == 1) l ++, ans ++;
            for(ll i = l; i <= r; i ++)
            {
                if(MillerRobin(i, 50)) ans ++;
                if(ans * 3 >= len) 
                {
                    puts("No");
                    bj = 1;
                    break;
                }
            }
            if(!bj) puts("Yes");
        }
	}
	return Sezuna;
}

F. The Answer to the Ultimate Question of Life, The Universe, and Everything.

题解：
真·打表题。
考虑暴力的复杂度是枚举 a³ + b³的和（复杂度10000*10000），然后二分找c³是否存在，但是明显得先将c³排序，O(10000log(10000))，复杂度显然已经超出1s了。
仔细观察发现x的范围只有0 - 200，所以可以先将所有x对应的a b c的情况打表打出来，然后复制放到二维数组里，直接输出答案。

`打表代码`：

#include <bits/stdc++.h>
#define inf 0x3f3f3f3f
#define fi first
#define se second
#define endl 'n'
#define Sezuna 0
#define IOS std::ios::sync_with_stdio(false),cin.tie(0), cout.tie(0)
#pragma GCC optimize(2) 
#pragma GCC optimize(3,"Ofast","inline")
using namespace std;

typedef long long ll;
const ll INF = 0x3f3f3f3f3f3f3f3f;
const int N = 1e6 + 100;

unordered_map<ll, int> f;


ll g(ll x)  //
{
	//x可能为负，也可能为正，所以需要从-5000开始
	for(ll i = -5000; i <= 5000; i ++)  //这里的i得用ll，因为下面关系到i^3的运算
		if(i * i * i == x)
			return i;
}

bool find(int x)
{
	for(ll i = 0; i <= 5000; i ++)  //这里可以分类讨论，减少循环次数，不用从-5000开始
	{
		for(ll j = 0; j <= 5000; j ++)
		{
			//x = -i -j +g
			if(f.count(x + i * i * i + j * j * j)) //如果存在这个c^3
			{
				printf("%lld, %lld, %lld,n", -i, -j, g(x + i * i * i + j * j * j));
				return true;
			}
			//x = +i +i -g
			else if(f.count(i * i * i + j * j * j - x)) //这里找的是正的g是否存在,而我们实际上的g是负的，所以开根之后要取负
			{
				// printf("%lld %lld %lld = %dn",i,j,g(i*i*i+j*j*j-x),x);
				printf("%lld, %lld, %lld,n", i, j, g(i * i * i + j * j * j - x) == 0 ? 0 : -g(i * i * i + j * j * j - x));
				return true;
			}
		}
	}
	return false;
}

int main()
{
	f.clear();
	 freopen("1.in", "w", stdout);
	for(ll i = -5000; i <= 5000; i ++)  //先用hash存下c^3的所有结果
		f[i * i * i] = 1;
	for(int i = 0; i <= 200; i ++)
	{
		if(!find(i)) printf("1111111111,0,0,n");
		else continue;
	}
	return Sezuna;
}

`AC代码:`

#include <bits/stdc++.h>
#define inf 0x3f3f3f3f
#define fi first
#define se second
#define endl 'n'
#define Sezuna 0
#define IOS std::ios::sync_with_stdio(false),cin.tie(0), cout.tie(0)
using namespace std;

typedef long long ll;
const ll INF = 0x3f3f3f3f3f3f3f3f;
const int N = 1e6 + 100;


int ans[205][3] = 
{
0, 0, 0,
0, 0, 1,
0, 1, 1,
1, 1, 1,
1111111111,1111111111,1111111111,
1111111111,1111111111,1111111111,
-1, -1, 2,
0, -1, 2,
0, 0, 2,
0, 1, 2,
1, 1, 2,
-2, -2, 3,
7, 10, -11,
1111111111,1111111111,1111111111,
1111111111,1111111111,1111111111,
2, 2, -1,
0, 2, 2,
1, 2, 2,
-1, -2, 3,
0, -2, 3,
1, 3, -2,
-11, -14, 16,
1111111111,1111111111,1111111111,
1111111111,1111111111,1111111111,
2, 2, 2,
-1, -1, 3,
0, -1, 3,
0, 0, 3,
0, 1, 3,
1, 1, 3,
1111111111,1111111111,1111111111,
1111111111,1111111111,1111111111,
1111111111,1111111111,1111111111,
1111111111,1111111111,1111111111,
2, 3, -1,
0, 2, 3,
1, 2, 3,
0, -3, 4,
1, 4, -3,
1111111111,1111111111,1111111111,
1111111111,1111111111,1111111111,
1111111111,1111111111,1111111111,
1111111111,1111111111,1111111111,
2, 2, 3,
-5, -7, 8,
2, 4, -3,
3, 3, -2,
6, 7, -8,
-2, -2, 4,
1111111111,1111111111,1111111111,
1111111111,1111111111,1111111111,
602, 659, -796,
1111111111,1111111111,1111111111,
-2, -4, 5,
0, 3, 3,
-1, -2, 4,
0, -2, 4,
1, 4, -2,
1111111111,1111111111,1111111111,
1111111111,1111111111,1111111111,
-1, -4, 5,
0, -4, 5,
-1, -1, 4,
0, -1, 4,
0, 0, 4,
0, 1, 4,
1, 1, 4,
1111111111,1111111111,1111111111,
1111111111,1111111111,1111111111,
2, 5, -4,
11, 20, -21,
2, 4, -1,
0, 2, 4,
1, 2, 4,
1111111111,1111111111,1111111111,
1111111111,1111111111,1111111111,
1111111111,1111111111,1111111111,
1111111111,1111111111,1111111111,
26, 53, -55,
-19, -33, 35,
2, 2, 4,
3, 3, 3,
-11, -11, 14,
-2, -5, 6,
1111111111,1111111111,1111111111,
1111111111,1111111111,1111111111,
1111111111,1111111111,1111111111,
-1972, -4126, 4271,
3, 5, -4,
6, 6, -7,
-1, -5, 6,
0, 3, 4,
1, 3, 4,
-5, -5, 7,
1111111111,1111111111,1111111111,
1111111111,1111111111,1111111111,
14, 20, -22,
-1, -3, 5,
0, -3, 5,
1, 5, -3,
-3, -6, 7,
4, 4, -3,
118, 229, -239,
1111111111,1111111111,1111111111,
1111111111,1111111111,1111111111,
-4, -7, 8,
2, 5, -3,
-28, -48, 51,
-948, -1165, 1345,
-2, -2, 5,
1111111111,1111111111,1111111111,
148, 1039, -1040,
1111111111,1111111111,1111111111,
1111111111,1111111111,1111111111,
1111111111,1111111111,1111111111,
-6, -10, 11,
-1, -2, 5,
0, -2, 5,
1, 5, -2,
-2, -6, 7,
4, 4, -2,
1111111111,1111111111,1111111111,
1111111111,1111111111,1111111111,
-1, -1, 5,
0, -1, 5,
0, 0, 5,
0, 1, 5,
0, -6, 7,
0, 4, 4,
1, 4, 4,
1111111111,1111111111,1111111111,
1111111111,1111111111,1111111111,
2, 5, -1,
0, 2, 5,
1, 2, 5,
2, 7, -6,
2, 4, 4,
-9, -11, 13,
-77, -86, 103,
1111111111,1111111111,1111111111,
1111111111,1111111111,1111111111,
2, 2, 5,
-3, -7, 8,
1111111111,1111111111,1111111111,
-2, -4, 6,
-7, -8, 10,
-5, -9, 10,
-50, -56, 67,
1111111111,1111111111,1111111111,
1111111111,1111111111,1111111111,
260, 317, -367,
-1, -4, 6,
0, 3, 5,
1, 3, 5,
3, 7, -6,
3, 4, 4,
1111111111,1111111111,1111111111,
1111111111,1111111111,1111111111,
1111111111,1111111111,1111111111,
80, 119, -130,
2, 3, 5,
-2, -7, 8,
-3, -3, 6,
-21, -26, 30,
-45, -47, 58,
1111111111,1111111111,1111111111,
1111111111,1111111111,1111111111,
1111111111,1111111111,1111111111,
-1, -7, 8,
0, -7, 8,
1, 8, -7,
-5, -6, 8,
1111111111,1111111111,1111111111,
1111111111,1111111111,1111111111,
7, 7, -8,
1111111111,1111111111,1111111111,
1111111111,1111111111,1111111111,
2, 8, -7,
-10, -13, 15,
3, 3, 5,
1111111111,1111111111,1111111111,
-2, -3, 6,
9, 13, -14,
10, 16, -17,
1111111111,1111111111,1111111111,
1111111111,1111111111,1111111111,
5, 5, -4,
27, 56, -58,
-1, -3, 6,
0, -3, 6,
1, 4, 5,
-3, -5, 7,
4, 4, 4,
1111111111,1111111111,1111111111,
1111111111,1111111111,1111111111,
1111111111,1111111111,1111111111,
3, 8, -7,
2, 4, 5,
-19, -48, 49,
15, 22, -24,
-2, -2, 6,
};


int main()
{
	int t;
	scanf("%d", &t);
	while(t --)
	{
		int x;
		scanf("%d", &x);
		if(ans[x][0] == 1111111111) puts("impossible");
		else printf("%d %d %dn", ans[x][0], ans[x][1], ans[x][2]);
	}
	return Sezuna;
}

Cat

（待补）
规律题。

用到的定理：

异或和定理：令f(n)表示从1到n的异或和，则：
　　　　　　若n≡0(mod4)，f(0,n)=n，
　　　　　　若n≡1(mod4)，f(0,n)=1，
　　　　　　若n≡2(mod4)，f(0,n)=n+1，
　　　　　　若n≡3(mod4)，f(0,n)=0。

若a是偶数，且a%4=(b+3)%4，则[a,b]的区间异或和为0。

异或运算的作用

参与运算的两个值，如果两个相应bit位相同，则结果为0，否则为1。

即：

0^0 = 0，

1^0 = 1，

0^1 = 1，

1^1 = 0

按位异或的3个特点：

（1） 0^0=0，0^1=1 0异或任何数＝任何数

（2） 1^0=1，1^1=0 1异或任何数－任何数取反

（3）任何数异或自己＝把自己置0

最后

以上就是忧伤保温杯为你收集整理的ICPC2019徐州区域赛复现赛C < 3 numbersF. The Answer to the Ultimate Question of Life, The Universe, and Everything.Cat的全部内容，希望文章能够帮你解决ICPC2019徐州区域赛复现赛C < 3 numbersF. The Answer to the Ultimate Question of Life, The Universe, and Everything.Cat所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。

本图文内容来源于网友提供，作为学习参考使用，或来自网络收集整理，版权属于原作者所有。

本文分类：Other
浏览次数：51 次浏览
发布日期：2023-11-11 16:15:04
本文链接：https://www.kaopuke.com/article/k-p-k_13_u_23_o_14_fx_13_zc0.html

ICPC2019徐州区域赛复现赛C < 3 numbersF. The Answer to the Ultimate Question of Life, The Universe, and Everything.Cat

概述

C < 3 numbers

F. The Answer to the Ultimate Question of Life, The Universe, and Everything.

`打表代码`：

`AC代码:`

Cat

异或运算的作用

最后

评论列表共有 0 条评论

发表评论取消回复

ICPC2019徐州区域赛复现赛C < 3 numbersF. The Answer to the Ultimate Question of Life, The Universe, and Everything.Cat

概述

C < 3 numbers

F. The Answer to the Ultimate Question of Life, The Universe, and Everything.

打表代码：

AC代码:

Cat

异或运算的作用

最后

相关文章

评论列表共有 0 条评论

发表评论 取消回复

`打表代码`：

`AC代码:`

发表评论取消回复