2012-0074

从 Trac 迁移的文章

这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。

原文章内容如下：

题目要求计算n+(n-1)x^2^  + (n-2)* x^3^+...+ x^(n-1)^  容易计算出和是 (x^(n+1)^ - x - n*x + n ) / (x-1)^2^ mod p
然后可以知道 结果= 分母mod p*分子 / 分子
然后无耻的java大数
{{{
import java.io.*; 
import java.util.*; 
import java.math.*; 




public class Main {
    public static void main(String[] args)
    {
         Scanner cin =new Scanner(System.in);
         while(cin.hasNext())
         {
             long tn=cin.nextLong();
             long tx=cin.nextLong();
             long tp=cin.nextLong();
             if(tn==0)
             {
                 System.out.println(0);
                 continue;
             }
             else if(tx==0)
             {
                 BigInteger n=new BigInteger("0");
                 BigInteger p=new BigInteger("0");
                 n=n.valueOf(tn);
                 p=p.valueOf(tp);
                 n=n.mod(p);
                 System.out.println(n.toString());
                 continue;
             }
             else if(tx==1)
             {
                 BigInteger n=new BigInteger("0");
                 BigInteger p=new BigInteger("0");
                 BigInteger temp=new BigInteger("0");
                 n=n.valueOf(tn);
                 p=p.valueOf(tp);
                 temp=n.subtract(n.ONE);
                 n=n.multiply(temp);
                 temp=temp.ONE;
                 temp=temp.add(temp.ONE);
                 n=n.divide(temp);
                 n=n.mod(p);
                 System.out.println(n.toString());
                 continue;
             }
             BigInteger MOU=new BigInteger("0");
             MOU=MOU.valueOf(tp);
             BigInteger a[]=new BigInteger[66];
             a[0]=a[0].ONE;
             a[1]=a[1].valueOf(tx);
             MOU=MOU.multiply(a[1].subtract(a[1].ONE));
             MOU=MOU.multiply(a[1].subtract(a[1].ONE));
             a[1]=a[1].mod(MOU);
             BigInteger n=new BigInteger("0");
             BigInteger x=new BigInteger("0");
             BigInteger p=new BigInteger("0");
             n=n.valueOf(tn);
             n=n.add(n.ONE);
             x=x.valueOf(tx);
             p=p.valueOf(tp);
             for(int i=2;i<=65;i++)
             {
                 a[i]=a[i-1].multiply(a[i-1]);
                 a[i]=a[i].mod(MOU);
             }
             int q[]=new int[66];
             int f=1;
             while(!n.equals(n.ZERO))
             {
                 BigInteger temp=new BigInteger("2");
                 temp=n.mod(temp);
                 q[f]=temp.intValue();
                 temp=temp.ONE;
                 temp=temp.add(temp.ONE);
                 n=n.divide(temp);
                 f=f+1;
             }
             BigInteger res=new BigInteger("1");
             for(int i=1;i<=65;i++)
             {
                 if(q[i]==1)
                 {
                     res=res.multiply(a[i]);
                     res=res.mod(MOU);
                 }
             }
             n=n.valueOf(tn);
             res=res.subtract(a[1]);
             res=res.add(n);
             n=n.multiply(a[1]);
             res=res.subtract(n);
             res=res.mod(MOU);
             res=res.add(MOU);
             res=res.mod(MOU);
             a[0]=a[1].subtract(a[1].ONE);
             res=res.divide(a[0]);
             res=res.divide(a[0]);
             System.out.println(res.toString());
         }
         cin.close();

    }
}

题目要求计算n+(n-1)x² + (n-2)* x³+...+ x^(n-1) 容易计算出和是 (x⁽ⁿ⁺¹⁾ - x - n*x + n ) / (x-1)² mod p

然后可以知道结果= 分母mod p*分子 / 分子

然后无耻的java大数

{{{

import java.io.*;

import java.util.*;

import java.math.*;

public class Main {

public static void main(String[] args)

{

Scanner cin =new Scanner(System.in);

while(cin.hasNext())

{

long tn=cin.nextLong();

long tx=cin.nextLong();

long tp=cin.nextLong();

if(tn==0)

{

System.out.println(0);

continue;

}

else if(tx==0)

{

BigInteger n=new BigInteger("0");

BigInteger p=new BigInteger("0");

n=n.valueOf(tn);

p=p.valueOf(tp);

n=n.mod(p);

System.out.println(n.toString());

continue;

}

else if(tx==1)

{

BigInteger n=new BigInteger("0");

BigInteger p=new BigInteger("0");

BigInteger temp=new BigInteger("0");

n=n.valueOf(tn);

p=p.valueOf(tp);

temp=n.subtract(n.ONE);

n=n.multiply(temp);

temp=temp.ONE;

temp=temp.add(temp.ONE);

n=n.divide(temp);

n=n.mod(p);

System.out.println(n.toString());

continue;

}

BigInteger MOU=new BigInteger("0");

MOU=MOU.valueOf(tp);

BigInteger a[]=new BigInteger[66];

a[0]=a[0].ONE;

a[1]=a[1].valueOf(tx);

MOU=MOU.multiply(a[1].subtract(a[1].ONE));

a[1]=a[1].mod(MOU);

BigInteger n=new BigInteger("0");

BigInteger x=new BigInteger("0");

BigInteger p=new BigInteger("0");

n=n.valueOf(tn);

n=n.add(n.ONE);

x=x.valueOf(tx);

p=p.valueOf(tp);

for(int i=2;i<=65;i++)

{

a[i]=a[i-1].multiply(a[i-1]);

a[i]=a[i].mod(MOU);

}

int q[]=new int[66];

int f=1;

while(!n.equals(n.ZERO))

{

BigInteger temp=new BigInteger("2");

temp=n.mod(temp);

q[f]=temp.intValue();

temp=temp.ONE;

temp=temp.add(temp.ONE);

n=n.divide(temp);

f=f+1;

}

BigInteger res=new BigInteger("1");

for(int i=1;i<=65;i++)

{

if(q[i]==1)

{

res=res.multiply(a[i]);

res=res.mod(MOU);

}

n=n.valueOf(tn);

res=res.subtract(a[1]);

res=res.add(n);

n=n.multiply(a[1]);

res=res.subtract(n);

res=res.mod(MOU);

res=res.add(MOU);

res=res.mod(MOU);

a[0]=a[1].subtract(a[1].ONE);

res=res.divide(a[0]);

System.out.println(res.toString());

}

cin.close();

}