K-消亡的质数-（简单数学）

https://ac.nowcoder.com/acm/contest/3346/K

题意：判断一个素数p是不是某两个数的立方差。

刚看到这道题一时半会都没有什么思路，看了题解恍然大悟，太久没碰数学或数论的，记录一下过程。

1.立方差公式：x³ - y³ = (x-y)(x²+ xy + y²)

2.(x-y)(x²+ xy + y²)=p

3.因为p是素数，所以x-y=1

4.将x=y+1带入原公式化简得 3y(y+1)=p-1

5.要使上式成立，(p-1)%3==0 && sqrt((p-1)/3) * (sqrt((p-1)/3)+1) == (p-1)/3

import java.util.Scanner;

public class Main {

    public static void main(String[] args) {

        Scanner scan=new Scanner(System.in);

        int n;

        n=scan.nextInt();

        long p;

        while(n!=0) {

            n--;

            p=scan.nextLong();

            if((p-1)%3==0) {

                p=(p-1)/3;

                long y=(long)Math.sqrt(p);//向下取整

                if(y*(y+1)==p)

                    System.out.println("YES");

                else

                    System.out.println("NO");

            }else

                System.out.println("NO");

        }

    }

}

巴特西

K-消亡的质数-（简单数学）

最新文章

热门文章