首页 > 其他分享 >[ARC158D] Equation

[ARC158D] Equation

时间:2023-05-28 22:33:56浏览次数:41  
标签:pw Equation ARC158D long leq 3n && 2n

Problem Statement

You are given a positive integer $n$, and a prime number $p$ at least $5$.

Find a triple of integers $(x,y,z)$ that satisfies all of the following conditions.

  • $1\leq x < y < z \leq p - 1$.
  • $(x+y+z)(x^n+y^n+z^n)(x^{2n}+y^{2n}+z^{2n}) \equiv x^{3n}+y^{3n}+z^{3n}\pmod{p}$.

It can be proved that such a triple $(x,y,z)$ always exists.

You have $T$ test cases to solve.

Constraints

  • $1\leq T\leq 10^5$
  • $1\leq n\leq 10^9$
  • $p$ is a prime number satisfying $5\leq p\leq 10^9$.

Input

The input is given from Standard Input in the following format:

$T$
$\text{case}_1$
$\vdots$
$\text{case}_T$

Each case is in the following format:

$n$ $p$

Output

Print $T$ lines. The $i$-th line should contain $x,y,z$ with spaces in between where $(x,y,z)$ is a solution for the $i$-th test case.

If multiple solutions exist, you may print any of them.


Sample Input 1

3
1 7
2 7
10 998244353

Sample Output 1

1 4 6
1 2 5
20380119 21549656 279594297

For the first test case:

  • $(x+y+z)(x^n+y^n+z^n)(x^{2n}+y^{2n}+z^{2n}) = (1+4+6)(1+4+6)(1+16+36) = 6413$, and
  • $x^{3n}+y^{3n}+z^{3n} = 1 + 64 + 216 = 281$.

We have $6413\equiv 281\pmod{7}$, so the conditions are satisfied.

本来以为拆开有什么用,后来又发现没有。

但是观察到两边是不齐次的,也就是说,如果设 \(x=ta%p,y=tb%p,z=tc%p\),那么我们可以随机出一个 \(a,b,c\),然后是可以解出 \(t\) 的

具体而言,设算出来左式= \(t^{6n}\times d\),右式为 \(t^{3n}\times e\),那么知道了 \(d\) 和 \(e\),可以解出 \(t\)

那么 \(d\) 和 \(e\) 要满足什么要求可以解出 \(t\) 呢?只要不都是 0 就行了。随机出来 \(a,b,c\),就可以算出 \(d\) 和 \(e\),容易发现,\(d\) 和 \(e\) 大概率不是0.

#include<bits/stdc++.h>
using namespace std;
int n,p,TME;
long long x,y,z,a,b,c,d,e,f,g;
mt19937_64 gen(time(0)) ;
long long pw(int x,long long y)
{
	if(!y)
		return 1;
	long long t=pw(x,y>>1);
	if(y&1)
		return t*t%p*x%p;
	return t*t%p; 
}
int main()
{
	scanf("%d",&TME);
	while(TME--)
	{
		scanf("%d%d",&n,&p);
		while(1)
		{
			x=gen()%(p-1)+1,y=gen()%(p-1)+1,z=gen()%(p-1)+1;
			if(x^y&&y^z&&z^x&&(x+y+z)%p&&(a=pw(x,n)+pw(y,n)+pw(z,n))%p&&(b=pw(x,n+n)+pw(y,n+n)+pw(z,n+n))%p&&(c=pw(x,n*3LL)+pw(y,n*3LL)+pw(z,n*3LL))%p)
			{	
				d=(x+y+z)%p*a%p*b%p;
				c=c*pw(d,p-2)%p;
				e=c*x%p,f=c*y%p,g=c*z%p;
				if(e>f)
					swap(e,f);
				if(e>g)
					swap(e,g);
				if(f>g)
					swap(f,g);
				printf("%lld %lld %lld\n",e,f,g);
				break;
			}
		}
	}
}

标签:pw,Equation,ARC158D,long,leq,3n,&&,2n
From: https://www.cnblogs.com/mekoszc/p/17439014.html

相关文章

  • [ARC144D] AND OR Equation
    ProblemStatementYouaregivenpositiveintegers$N$and$K$.Findthenumber,modulo$998244353$,ofintegersequences$\bigl(f(0),f(1),\ldots,f(2^N-1)\bigr)$thatsatisfyallofthefollowingconditions:$0\leqf(x)\leqK$forallnon-negative......
  • 15 Ray Tracing (Rendering Equation)
    关键点BRDF(BidirectionalReflectanceDistributionFunction)ReflectionEquationRenderingEquation1.BidirectionalReflectanceDistributionFunction(BRDF)1.1BRDF反射可以理解为光线打到物体表面被吸收,然后按照某些方向再辐射出去一部分。BRDF定义了从某一个......
  • Topcoder 10880 - Functional Equation
    首先分析一下这个鬼畜的函数,我们考虑\(f(x)+2C\)\(=f(2f(x)-x+1)+C\)\(=f(2f(2f(x)-x+1)-(2f(x)-x+1)+1)\)\(=f(2(f(x)+C)-2f(x)+x-1+1)\)\(=f(x+2C)\)也就是\(f(x)=f(x\bmod2C)+2C\lfloor\dfrac{x}{2C}\rfloor\)也就是,只要决定了\(f(x)\),\(f(x+2mC)\)也就被确定了。......
  • AtCoder Regular Contest 158 D - Equation
    题目链接原本看着式子直接晕了,觉得是高深的硬核数论,于是放弃(然后E也没想出来,sad)关键的思路在于,考虑构造由(a,b,c)->(ta,tb,tc)这样的求解方式。在看到这个做法后,会发现它很好地利用了题目齐次的性质;至于如何由齐次式想到这个做法,可能需要足够的天赋或者经验吧(悲)化简后得到\(At......
  • MATH1851 Ordinary differential equations
    课程内容笔记,自用,不涉及任何assignment,exam答案Notesforself-use,donotincludeanyassignmentsorexamsMATH1851的第二节:主要学习常微分方程ODE:Ordinary......
  • 「解题报告」ARC158D Equation
    好神仙的题。考虑形如\(F(x,y,z)=x^i+y^i+z^i\)的函数有一个性质:\(F(tx,ty,tz)=t^iF(x,y,z)\)。原式要求\((x+y+z)(x^n+y^n+z^n)(x^{2n}+y^{2n}+z^{2n......
  • HDU2199 Can you solve this equation? (二分查找)
    Canyousolvethisequation?TimeLimit:2000/1000MS(Java/Others)    MemoryLimit:32768/32768K(Java/Others)TotalSubmission(s):12794    AcceptedS......
  • MATH1851 Calculus and ordinary differential equations
    课程内容笔记,自用,不涉及任何assignment,exam答案Notesforselfuse,notincludedanyassignmentsorexams由于提前预习了微积分(见微积分\(I\),微积分\(II\))......
  • Functions, Equations and Polynomials (Pure Math)
    MO题乱做\(f:\mathbb{N}^*\mapsto\mathbb{N}^*,\foralln\in\mathbb{N}^*,f(f(n))<f(n+1)\).求\(f(n)\).有一个很厉害的做法.首先我们证明\(f(1)\)是\(\{f(k)|......
  • The Human Equation
    TheHumanEquation关键赛后随便猜了一下,竟然过了。只能说当时还是太急了,毕竟对E多少有点害怕。不行,以后要到能出E的水平代码#include<bits/stdc++.h>usingnamespa......