[ZJ][規律] a568. ISSC 2012- problem B＠Morris' Blog

2012-11-22 08:25:32| 人氣767| 回應0 | 上一篇 | 下一篇

[ZJ][規律] a568. ISSC 2012- problem B

推薦 0 收藏 0 轉貼0 訂閱站台

內容：

給定一個數字N，代表這個數字有2N位數，

我們先定義 Good number

當我們把一個數字切一半

( ez. 1981 切一半變成 19 和 81 )

當他切一半後的兩個數字都可以整除原本的數字時，

這個數字就是Good Number

例如 2244

22 可以整除 2244 , 44 也可以整除 2244

所以2244是一個Good number

本題是要你找2N位的數字中有幾個Good number

噢~ 任何Good number 分成的左右兩半都不可以有數字0

ex 2200 ( 除以0是不合法的 )

輸入說明：

多筆輸入

每行有兩個正整數N, M

1 <= N <= 7000007 , 2 <= M <= 10000

( 原本題目是只有到8 )

輸出說明：

請輸出位數為2N的Good number 有幾個

，因為答案可能很大，請輸出 modulo M 的結果

範例輸入： help

1 25
2 150

範例輸出：

14
5

提示：

1. 70% 分數的測資 N <= 5 , M <= 100

2. 25% 分數的測資 N <= 8 , M <= 1000

3. 4 % 分數的測資 N <= 10 , M <= 10000

4. 1 % 分數的測資 N <= 7000007 , M <= 10000

hint : please use brute force if you want to get 95 points

PS. 時間開到最寬了~

出處：

ISSC 2012 (管理：stanley17112000)

暴搜幾筆之後找規律即可

14
155
1575
15750
157500

/**********************************************************************************/
/* Problem: a568 "ISSC 2012- problem B" from ISSC 2012                           */
/* Language: CPP (599 Bytes)                                                     */
/* Result: AC(217ms, 249KB) judge by this@ZeroJudge                              */
/* Author: morris1028 at 2012-11-20 23:09:41                                     */
/**********************************************************************************/

#include <stdio.h>
int mypow(int x, int y, int mod) {
    if(!y)   return 1;
    if(y&1)
        return x*mypow(x*x%mod, y>>1, mod)%mod;
    return mypow(x*x%mod, y>>1, mod);
}
int main() {
    int n, m, tmp, i;
    while(scanf("%d %d", &n, &m) == 2) {
        if(n == 1) printf("%d\n", 14%m);
        else if(n == 2) printf("%d\n", 155%m);
        else if(n == 3) printf("%d\n", 1575%m);
        else {
            tmp = 1575%m;
            tmp = tmp*mypow(10, n-3, m)%m;
            printf("%d\n", tmp);
        }
    }
    return 0;
}
/*
14
155
1575
15750
157500
*/

我要檢舉

#a568#ISSC 2012- problem B

台長： Morris

您可能對以下文章有興趣

a121. 質數又來囉

[ZJ][LCA][online] d767. 血緣關係

[ZJ][Greedy、並查集] a567. 死線排程

[ZJ][圓并、圓交、周長] a648. A - Red Areas

人氣(767) | 回應(0)| 推薦 (0)| 收藏 (0)| 轉寄
全站分類: 不分類 | 個人分類: ZeroJudge |
此分類下一篇:[ZJ][dp] a578. 苦哈哈機器人工廠
此分類上一篇:[ZJ][BIT] a572. IS&MS

回應(0)