程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> 10162 - Last Digit (數論+周期規律)

10162 - Last Digit (數論+周期規律)

編輯:C++入門知識

UVA 10162 - Last Digit

題目鏈接

題意:求S=(11+22+...NN)%10

思路:打出0-9的每個周期,發現周期為1或2或4、所以S是以20一個周期,打出表後發現20為4,所以對應的40為8,60為2,80為6,100為0,100為1個周期,且為0,所以先把數字mod上100,然後在mod 20求出對應位置。

代碼:

#include 
#include 

const int Z2[10] = {0, 4, 8, 2 ,6};
int T[10][10], tn[10];
int Z[25];
char str[105];

int solve(int mod) {
    int len = strlen(str);
    int yu = 0;
    for (int i = 0; i < len ;i++) {
	yu = (yu * 10 + str[i] - '0') % mod;
    }
    return yu;
}

int main() {
    for (int i = 0; i < 10; i++) {
	int tmp = i;
	T[i][tn[i]++] = i;
	tmp = tmp * i % 10;
	while (tmp != i) {
	    T[i][tn[i]++] = tmp;
	    tmp = tmp * i % 10;
	}
    }
    for (int i = 1; i <= 20; i++) {
	int tmp = i % tn[i % 10] - 1;
	if (tmp < 0) tmp += tn[i % 10];
	Z[i] = (Z[i - 1] + T[i % 10][tmp]) % 10;
    
    }
    /*for (int i = 1; i <= 20; i++)
	printf("%d\n", Z[i]);
    for (int i = 0; i < 10; i++) {
	printf("%d: zhouqi %d:\n", i, tn[i]);
	for (int j = 0; j < tn[i]; j++)
	    printf("%d ", T[i][j]);
	printf("\n");
    }*/
    while (~scanf("%s", str) && str[0] != '0') {
	int yu = solve(100);
	int ans = (Z[yu % 20] + Z2[yu / 20]) % 10;
	printf("%d\n", ans);
    }
    return 0;
}


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