奥数选拔题

有多少组 0 至 70 之间的整数 (x, y, z) 使得

13 x^2 y + 4 x^4 z^3 + 5 x^3 y^5 z^6 + 3 y^7 z^16

可以被 71 整除？

P.S. 各位其实也可以编个程序去靠硬算来求解，把每个 (x, y, z) 的组合全试一遍也用不了多少 Machine runtime。:titter:

[[i] 本帖最后由 天宫公主 于 2008-2-14 13:51 编辑 [/i]]

这是我等闲人该干的事情吗?

更正上贴回复,
这是人该干的事儿吗?

作为论坛娱乐，能否先给点提示或者解题方向之类的说……

做不出来，我彻底变成计算机的奴隶了。

只会P.S.里的方法:-_-:

机算了下，412个。
除去x，z都等于0的71个，还有……341个。
奥数有时间的吧……且这个东西要是写在试卷上，能写完么？
————————————————————————————————————
式子列错了…………

貌似有5457组啊。颇夸张了点
---------------------------------------------------------------------------------------------------
天哪，我写程序的能力骤然衰减……居然又错了
---------------------------------------------------------------------------------------------------
小帖一下程序，下班回去再研究：

package fd.misc;

public class Math1 {
        private static final int LIMIT_LOW = 0;

        private static final int LIMIT_HI = 70;

        static int x, y, z;

        /**
         * @param args
         */
        public static void main(String[] args) {
                int count = 0;

                for (x = LIMIT_LOW; x <= LIMIT_HI; x++) {
                        for (y = LIMIT_LOW; y <= LIMIT_HI; y++) {
                                for (z = LIMIT_LOW; z <= LIMIT_HI; z++) {
                                        double result = getResult();

                                        if (result % 71 == 0) {
                                                System.out.println("x=" + x + ",y=" + y + ",z=" + z);
                                                count++;
                                        }
                                }
                        }
                }

                System.out.println(count);
        }

        private static double getResult() {
                return getUnit(13, 2, 1, 0) + getUnit(4, 4, 0, 3) + getUnit(5, 3, 5, 6)
                                + getUnit(3, 0, 7, 16);
        }

        private static double getUnit(int n, int xn, int yn, int zn) {
                return n * Math.pow(x, xn) * Math.pow(y, yn) * Math.pow(z, zn);
        }
}

[[i] 本帖最后由 fantasydog 于 2008-2-16 14:29 编辑 [/i]]

汗一下楼上的程序，够结构化
问题是，double能用么? java里有没有任意精度整数类型？
话说我的程序跑出来是5083组
顺便赞一下python: "Long integers have unlimited precision"
pow(70, 16) = 332329305696010000000000000000L
pow(2, 64) = 18446744073709551616L

[[i] 本帖最后由 smalltalk 于 2008-2-16 15:49 编辑 [/i]]

5083是对的。
double太大时，模一个比较小的数就模不出来了。
修改后：
package fd.misc;

public class Math1 {
        private static final int LIMIT_LOW = 0;

        private static final int LIMIT_HI = 70;
       
        private static final int MAGIC_NUM = 71;

        static int x, y, z;

        /**
         * @param args
         */
        public static void main(String[] args) {
                int count = 0;

                for (x = LIMIT_LOW; x <= LIMIT_HI; x++) {
                        for (y = LIMIT_LOW; y <= LIMIT_HI; y++) {
                                for (z = LIMIT_LOW; z <= LIMIT_HI; z++) {
                                        double result = getResult();

                                        if (result % 71 == 0) {
                                                System.out.println("x=" + x + ",y=" + y + ",z=" + z);
                                                count++;
                                        }
                                }
                        }
                }

                System.out.println(count);
        }

        private static double getResult() {
                return getUnit(13, 2, 1, 0) + getUnit(4, 4, 0, 3) + getUnit(5, 3, 5, 6)
                                + getUnit(3, 0, 7, 16);
        }

        private static double getUnit(int n, int xn, int yn, int zn) {
                return n * pow(x, xn) * pow(y, yn) * pow(z, zn);
        }

        private static int pow(int x2, int xn) {
                int result = 1;
                for(int i=0;i<xn;i++) {
                        result = result * x2;
                       
                        result %= MAGIC_NUM;
                }
                return result;
        }
}

PS：对这类问题结构化就够了吧，难道用topcoder的模式写？

[[i] 本帖最后由 fantasydog 于 2008-2-16 16:40 编辑 [/i]]

这个。。。5083 肯定有问题的，总数应该不大于 71^2=5041。我也再自己检查一下。。。

main()
{
        int x,y,z,i,j;
        int sum1,sum2,sum3,sum4,sum,count;
        int mod[71][17];
        for(i=0;i<71;i++)
                for(j=0;j<17;j++)
                        if(j==0)
                                mod[i][j]=1;
                        else
                                mod[i][j]=mod71(mod[i][j-1]*i);
        count=0;
        for(x=0;x<71;x++)
                for(y=0;y<71;y++)
                        for(z=0;z<71;z++)
                        {
                                sum1=mod71(13*mod[x][2]*mod[y][1]);
                                sum2=mod71(4*mod[x][4]*mod[z][3]);
                                sum3=mod71(5*mod[x][3]*mod[y][5]*mod[z][6]);
                                sum4=mod71(3*mod[y][7]*mod[z][16]);
                                sum=mod71(sum1+sum2+sum3+sum4);
                                if(sum==0)
                                        count++;
                        }
        printf("%d\n",count);
}

子程序略，答案是5083。问题是用数学方法怎么做呢。

如果 5083 是正确答案，说明我的“数学方法”似乎有错误，我再好好检查一下吧。