CodeForces 248B Chilly Willy

题目:

Description
Chilly Willy loves playing with numbers. He only knows prime numbers that are digits yet. These numbers are 2, 3, 5 and 7. But Willy grew rather bored of such numbers, so he came up with a few games that were connected with them.
Chilly Willy wants to find the minimum number of length n, such that it is simultaneously divisible by all numbers Willy already knows (2, 3, 5 and 7). Help him with that.
A number's length is the number of digits in its decimal representation without leading zeros.
Input
A single input line contains a single integer n (1 ≤ n ≤ 105).
Output
Print a single integer — the answer to the problem without leading zeroes, or "-1" (without the quotes), if the number that meet the problem condition does not exist.
Sample Input
Input
1
Output
-1
Input
5
Output
10080

给定一个数n,要你找出一个数,这个数有n位且是最小的能被2,3,5,7都整除的数。
n的范围很大,因此不能直接去做。
事实上,能被2,3,5,7都整除的数就是能被210整除的数(最小公倍数)。通过观察,我们可以发现只需考虑后3位数即可,最后一位一定是0,所以只需考虑倒数第三位和倒数第二位即可。通过运算我们可以找到规律:从n = 4开始,6个为一个循环。

参考代码:

#include <iostream>
#include <cstdio>
using namespace std;

char str[7][3] = {"05", "08", "17", "02", "20", "11"};

void print(const int n) {
    if (n == 1 || n == 2) cout << "-1" << endl;
    else if (n == 3) cout << "210" << endl;
    else {
        int temp = (n - 4) % 6;
        printf("1");
        for (int i = 0;i < n - 4;++i) {//剩余位补0;
            printf("0");
        }
        printf("%s0\n", str[temp]);
    }   
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    int n;
    cin >> n;
    print(n);
    return 0;
}

其实我开始也不知道这个题的规律,是看了网上大神们的博客才知道这个规律的,还是大神们厉害。

最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容

  • **2014真题Directions:Read the following text. Choose the be...
    又是夜半惊坐起阅读 9,917评论 0 23
  • 今天照例去菜摊买菜,摊主把我的菜结完帐,然后随手拿起来塑料袋,就要往里面装。我赶忙制止他,告诉他我不用塑料袋,自己...
    Cola猫咪阅读 191评论 0 0
  • 我也不知道为啥要写这个,可能是看到老同学发给我她写的文章,有点感触,感觉时光真的就这么匆匆而过了,然后,什么都...
    M莫名M阅读 316评论 0 1
  • 所有商业行为都有一只看不见的手在控制,这只手就是供需关系,市场经济商业行为归根结底就是供和需,供需对接,形成交易。...
    东岳不是泰山阅读 338评论 0 0
  • 每路过一扇窗 我总会带走些屋子里的东西 窗外飘着的 是烹饪晚餐的香气 忙忙碌碌了一天 环绕着幸福的慰藉 窗口穿出来...
    超超级高中生阅读 266评论 0 1