首页 > 其他分享 >poj-2635

poj-2635

时间:2023-05-23 16:02:21浏览次数:44  
标签:10 2635 curVal long int length poj 整除


// 1652K    875MS   G++ 1000
// 1648K   1313MS  G++ 10000
#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>

const int MAX = 1000100;

char notPrime[MAX+1];

int PrimeNum;
int Primes[MAX];

void checkPrime() {
    notPrime[0] = 1;
    notPrime[1] = 1;
    notPrime[2] = 0;
    for (int i = 2; i <= (int)sqrt(MAX) + 1; i++) {
        int k = 2;
        while(k * i <= MAX) {
            notPrime[k * i] = 1;
            k++;
        }
    }

    PrimeNum = 0;
    for (int i = 2; i <= MAX; i++) {
        if (!notPrime[i]) {
            Primes[PrimeNum++] = i;
            // printf("%d\n", i);
        }
    }
}

char BigNum[103];
int L;

int Kt[34];

void solve(char * bigNum, int L) {
    int curLength = strlen(bigNum);
    int KtLength = 0;

    int units_length = 3;

    while (curLength > 0) {
        int curVal = 0;
        if (curLength >= units_length) {
            curVal = atoi(bigNum + curLength - units_length);
            *(bigNum + curLength - units_length) = 0;
        } else {
            curVal = atoi(bigNum);
        }
        Kt[KtLength++] = curVal;
        // printf("%d\n", curVal);
        curLength -= units_length;
    }

    char good = 1;
    int badNum = 0;
    int Units_Val = pow(10, units_length);
    for (int i = 0; Primes[i] < L; i++) {
        int curPrime = Primes[i];
        int reminder = 0;
        for (int j = KtLength - 1; j >= 0; j--) {
            long long curVal = (long long)Kt[j] + (long long)reminder * Units_Val;
            reminder = curVal % curPrime;
            if (j == 0) {
                if (reminder == 0) {
                    good = 0;
                    badNum = curPrime;
                }
            }
        }
        if (!good) {
            break;
        }
    }

    if (good) {
        printf("GOOD\n");
    } else {
        printf("BAD %d\n", badNum);
    }
}

int main() {
    checkPrime();
    while(scanf("%s %d", BigNum, &L) != EOF) {
        // printf("%s %d\n", BigNum, L);
        if (BigNum[0] == '0' && L == 0) {
            return 0;
        }
        solve(BigNum, L);
    }
}



一道很好的数论题,学到了另外一种表示大数的方式: 大进制(一般都是千), 基本思路其实很朴素,首先对于输入的大数N 和 factorL,

用所有比L小的素数 对N进行整除测试,如果存在比L小的素数可以整除N的话,那么就是BAD, 并且输出此最小的素数,

因为题目给了L最多到1000000,因此,只要事先把所有比L小的素数都搞出来就足够题目中使用了,至于求法,直接用素数筛子即可,没啥技术含量。

然后就是判断某个素数K是否能整除N了,因为N是大数,因此不可能用基本类型来表示,而如果用传统的字符串法来表示N,那么判断整除将会非常麻烦,

这时候,就轮到大进制出场了,为了方便起见,用千进制(意思很好理解,就是基本的进制,只不过从10变成了1000),这样,用一个int数组就可以表示此大数了(N最多到10的100次方,因此可以预先分配足够的空间), 而如何判断整除,也要用到一些数学trick(直接除铁定不行,要一位一位的进行),

举个例子,对于十进制的数 5678, 判断其是否可以被3整除,可以采用这样的一位一位处理方法:

首先最高位 5 %3 = 2,        

那么下一位:  (3*10 + 6) % 3 = 0

继续: (0*10 + 7) % 3 = 1

继续:  (1*10 + 8)%3 = 0

因为最后一次求余为0,因此5678可以被3整除。

这个trick其实很简单,就是小学级别的,算法概论也对求余这种运算很推崇,称其解决了一部分计算机大数的问题,因为很多时候,我们只关心余数,而不关心除数,因此,这时候,同余定理就很有用.

后来改成了万进制试了一把,发现速度反而降了,

还犯了基础问题,

long long curVal = Kt[j] + reminder * Units_Val;

在万进制时,后面两个会溢出(因为都是int型),不会因为赋值那边是long long就自动扩展的.

不过用char做同样操作,却没出错,因为

C++算术转换规则:小于整型的数值总会先被转换成整型,这个规则一般称作整形提升。

标签:10,2635,curVal,long,int,length,poj,整除
From: https://blog.51cto.com/u_9420214/6332985

相关文章

  • poj-3286
    //stupidmethod!!!!!!!!!!!!!!!//388K360MSG++#include<stdio.h>#include<string.h>#include<math.h>intC[33][33];//C[n][m],choosemfromn;voidgetCombination(){for(intn=0;n<=32;n++){for(intm=......
  • poj-2282
    //380K 32MS G++#include<stdio.h>#include<string.h>#include<math.h>longlongappearTime1[10];longlongappearTime2[10];voidgetAppearTime(intnum,longlong*appearArray){ appearArray[0]=1; if(num==0){ return; }......
  • poj-2249
    //356K16MSG++//356K0MSG++addm==0check//356K16MSG++//356K0MSG++addm==0check#include<stdio.h>#include<string.h>#include<math.h>intm;intn;//voidgetNum(unsignedintn,unsignedintm){//......
  • poj-1037
    //196K16MSC++#include<cstdio>#include<cstring>usingnamespacestd;constintMAX=25;longlongDP[MAX][MAX][2];//0:down.1:upvoidinit(){for(intcurPlankNum=1;curPlankNum<=20;curPlankNum++){for(......
  • poj-2140
    //132K 110MS C++#include<cstring>#include<cstdio>usingnamespacestd;intN;longlongcnt;voidsolve(intN){ intbegin=1; intend=1; longlongsum=1; while(1){ if(begin>N){ break; } //if(begin==......
  • poj-1988
    //564K 282MS C++#include<cstdio>#include<cstring>#include<iostream>usingnamespacestd;structUF_Node{ intup; intcount; intparent;};typedefstructUF_NodeUF_Node;UF_NodeUF_Array[30001];voidcreat(){ intc; for(......
  • poj-1693
    //136K 0MS C++#include<cstdio>#include<cstring>structLine{ intbx,ex; intby,ey;};typedefstructLineLine;LinehLine[110];LinevLine[110];intcaseNum;intLineNum;boolinsect(Line&vline,Line&hline){ //pr......
  • POJ1737 Connected Graph ( n点无向连通图计数
    题意说明:求\(n\)个点的无向连通图个数据说已经非常典了,但是我太菜了不会组合数学,最近补档时看到这道题,决定记录下来理理思路......
  • POJ--1163 The Triangle(DP)
    记录10:432023-5-15http://poj.org/problem?id=1163reference:《挑战程序设计竞赛(第2版)》第二章练习题索引p135DescriptionFigure1showsanumbertriangle.Writeaprogramthatcalculatesthehighestsumofnumberspassedonaroutethatstartsatthetopa......
  • 实验六-Salt本地pojie实验
    【实验目的】了解Salt型密码的加密机制,学会使用本地密码pojie工具来pojieSalt型密码,了解pojie密码原理。【知识点】Salt,密码pojie【实验原理】1.Salt概念在密码保护技术中,salt是用来修改口令散列的随机数据串。可将salt加入散列,即使系统的另一用户也选用了同一口令,也可通过唯......