杭电ACM课件学习 简单数学题

抓紧时间练java。

1.模拟；杭电1008

比较简单的模拟题

java

import java.io.*;

import java.util.*;

public class Main

{

    public static void main(String args[])

    {

        Scanner cin = new Scanner(System.in);

        int n, sum;

        int[] line = new int[100];

        line[0] = 0;

        while(cin.hasNextInt())

        {

            n = cin.nextInt();

            if(n == 0) break;

            sum = 0;

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

            {

                line[i] = cin.nextInt();

                sum += line[i]-line[i-1]>0?(line[i]-line[i-1])*6+5:(line[i-1]-line[i])*4+5;

            }

            System.out.println(sum);

        }

    }

}

2.最小公倍数； 杭电1108

java

import java.io.*;

import java.util.*;

public class Main

{

    private static int gcd(int large, int small)

    {

        int temp;

        while(small != 0)

        {

            temp = large%small;

            large = small;

            small = temp;

        }

        return large;

    }

    public static void main(String args[])

    {

        Scanner cin = new Scanner(System.in);

        int a, b, re;

        while(cin.hasNextInt())

        {

            a = cin.nextInt();

            b = cin.nextInt();

            re = a > b?gcd(a, b):gcd(b, a);

            System.out.println(a*b/re);

        }

    }

}

3.rightmost digit ；杭电1061

简单想法-超时

java

import java.io.*;

import java.util.*;

public class Main

{

    public static void main(String args[])

    {

        Scanner cin = new Scanner(System.in);

        int a, rd, n;

        n = cin.nextInt();

        for(int i = 0; i < n; i++)

        {

        rd = 1;

            a = cin.nextInt();

            for(int j = 0; j < a; j++)

            {

            rd *= a%10;

            rd %= 10;

            }

            System.out.println(rd);

        }

    }

}

快速模幂 （二分加速）

java

import java.io.*;

import java.util.*;

public class Main

{

    public static void main(String args[])

    {

        Scanner cin = new Scanner(System.in);

        int a, rd, n, p;

        n = cin.nextInt();

        for(int i = 0; i < n; i++)

        {

            rd = 1;

            a = cin.nextInt();

            p = a;

            while(p != 0)

            {

                a %= 10;

                if(p%2 == 1) 

                {

                    rd = rd*a%10;  //主要是这里别溢出 等价于rd = (rd*a)%10

                }

                a *= a;

                p >>= 1;

            }

            System.out.println(rd);

        }

    }

}

int num[21]={0,1,4,7,6,5,6,3,6,9,0,1,6,3,6,5,6,7,4,9,0};

杭电2035

java

import java.io.*;

import java.util.*;

public class Main

{

    public static int fastpower(int a, int p, int mod)

    {

        int rd = 1;

        while(p != 0)

        {

            a %= mod;

            if(p%2 == 1) 

            {

                rd = rd*a%mod;  

            }

            a *= a;

            p >>= 1;

        }

        return rd;

    }

    public static void main(String args[])

    {

        Scanner cin = new Scanner(System.in);

        int a, p;

        while(cin.hasNextInt())

        {

            a = cin.nextInt();

            p = cin.nextInt();

            if(a == 0 && p == 0) break;

            System.out.println(fastpower(a, p, 1000));

        }

    }

}

4.fibonacci again

java

超时版

import java.io.*;

import java.util.*;

public class Main

{

public static int fibonacci(int n)

{

if(n == 0) return 7;

if(n == 1) return 11;

return fibonacci(n-1)+fibonacci(n-2);

}

    public static void main(String args[])

    {

        Scanner cin = new Scanner(System.in);

        int a;

        while(cin.hasNextInt())

        {

        a = cin.nextInt();

        if(fibonacci(a)%3 == 0)

        System.out.println("yes");

        else System.out.println("no");    

        }

    }

}

加速版

import java.io.*;

import java.util.*;

public class Main

{

    public static void main(String args[])

    {

        Scanner cin = new Scanner(System.in);

        int a;

        int[] fib = new int[1000010];

        fib[0] = 7;

        fib[1] = 11;

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

        {

            fib[i] = (fib[i-1] + fib[i-2])%3;//小心溢出

        }

        while(cin.hasNextInt())

        {

            a = cin.nextInt();

            if(fib[a]%3 == 0)

                System.out.println("yes");

            else System.out.println("no");        

        }

    }

}

极速版

import java.io.*;

import java.util.*;

public class Main

{

    public static void main(String args[])

    {

        Scanner cin = new Scanner(System.in);

        int a;

        while(cin.hasNextInt())

        {

            a = cin.nextInt();

            if(a%4 == 2)                 //总结规律

                System.out.println("yes");

            else System.out.println("no");        

        }

    }

}

5.number sequence 根据数论，取模运算必有周期 1005这题有问题，可以简单看一下

6.杭电1205

BigInteger练习

import java.io.*;

import java.util.*;

import java.math.*;

public class Main

{

    public static void main(String args[])

    {

        Scanner cin = new Scanner(System.in);

        int n, max;

        BigInteger sum, tmp;

        n = cin.nextInt();

        for(int i = 0; i < n; i++)

        {

        max = 0;

                sum = BigInteger.valueOf(1);

        int cnt = cin.nextInt();

        for(int j = 0; j < cnt; j++)

        {

        int a = cin.nextInt();

        if(a > max) max = a;

                    tmp = BigInteger.valueOf(a);

        sum = sum.add(tmp);

        }

        sum = sum.divide(BigInteger.valueOf(2));

        sum = sum.add(BigInteger.valueOf(1));

        BigInteger tmax = BigInteger.valueOf(max);

        if(tmax.compareTo(sum) == -1)

        System.out.println("Yes");

        else System.out.println("No");

        }

    }

}

import java.io.*;

import java.util.*;

public class Main

{

    public static void main(String args[])

    {

        Scanner cin = new Scanner(System.in);

        int n, l;

        long sum = 0;//这个是long就行

        n = cin.nextInt();

        for(int i = 0; i < n; i++)

        {

            sum = 0;

            l = 0;

            int cnt = cin.nextInt();

            for(int j = 0; j < cnt; j++)

            {

                int a = cin.nextInt();

                if(a > l) l = a;

                sum += a;

            }

            sum = (sum+1)/2+1;

            if(l < sum)

                System.out.println("Yes");

            else System.out.println("No");

        }

    }