程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> poj 2551 Ones and poj 2262 Goldbachs Conjecture

poj 2551 Ones and poj 2262 Goldbachs Conjecture

編輯:C++入門知識

第一個題用到了同余的性質,這是數論裡面最基本的性質,但是做題時候不一定能夠自己發現。題意是n*m = 11111...,給出n,
用一個m乘以n得到的答案全是1組成的數字,問1最小的個數是多少。可以轉換為n*m=(k*10+1),那麼可以得到(k*10+1)%n==0。
當然最開始的k是1,那麼我們不斷的增長k = (10*k+1)。看增長多少次,就是有多少個1了。因為要避免溢出,所以需要不斷%n。
因為同余的性質,所以可以保證%n之後答案不變。
   第二個用到素數篩選法。素數篩選法的原理是篩去素數的倍數,由於是從小循環到大的,所以當前的值沒被篩掉的話,則一定是素數,
這個判斷導致復雜度不是n的平方。

   poj 2551 代碼:
  
#include <stdio.h>
int main()
{
    int nN;
   
    while (scanf("%d", &nN) == 1)
    {
        int nCnt = 1;
        int nTemp = 1;
        while (1)
        {
            if (nTemp % nN == 0)break;
            else nTemp = (nTemp * 10 + 1) % nN;
            ++nCnt;
        }
        printf("%d\n", nCnt);
    }
   
    return 0;
}
   poj 2262 代碼:
#include <stdio.h>
#include <string.h>
#include <math.h>

#define MAX (1000000 + 10)
bool bPrime[MAX];
void InitPrime()
{
    memset(bPrime, true, sizeof(bPrime));
    bPrime[0] = bPrime[1] = false;
    for (int i = 2; i <= MAX; ++i)
    {
        if (bPrime[i])
        for (int j = 2 * i; j <= MAX; j += i)
        {
            bPrime[j] = false;
        }
    }
}

int main()
{
    int nN;
   
    InitPrime();
    while (scanf("%d", &nN), nN)
    {
        int i;
        for (i = 2; i < nN; ++i)
        {
            if (i % 2 && (nN - i) % 2 && bPrime[i] && bPrime[nN - i])
            {
                printf("%d = %d + %d\n", nN, i, nN - i);
                break;www.2cto.com
            }
        }
        if (i == nN)
        {
            printf("Goldbach's conjecture is wrong.\n");
        }
    }
   
    return 0;
}
 

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved