计算日期(快速幂+打表) - ZOJ 3785

新来的紫芝眉宇,参加过亚洲区域赛晋级

It's Saturday today, what day is it after11 + 22 + 33 + ... + NN days?

Input

There are multiple test cases. The firstline of input contains an integer T indicating the number of test cases. Foreach test case:

There is only one line containing oneinteger N (1 <= N <= 1000000000).

Output

For each test case, output one stringindicating the day of week.

Sample Input

2

1

2

Sample Output

Sunday

Thursday

Hint

A week consists of Sunday, Monday, Tuesday,Wednesday, Thursday, Friday and Saturday.

题意:

今天星期六,求1^1+2^2……N^N天后是星期几

思路:

同余与模算术,利用快速幂取模的算法,时间复杂度为O(logn)。

1.先用快速幂求出11 , 22 +,33 , ... ,NN

对7取模之后的结果,发现循环节长度为42,即

(1^1)%7=(43^43)%7,

(2^2)%7=(44^44)%7,

(3^3)%7=(45^45)%7,

(n^n)%7=( (42+n)^(42+n) )%7

源代码:

#include<bits/stdc++.h>
using namespace std;

int fast_pow(int a, int n, int mod)
{
  int ret = 1;

  while (n)
  {
    if (n & 1)
      ret = ret * a % mod;

    a = a * a % mod;
    n >>= 1;
  }

  return ret;
}

int main()
{

  for (int i = 1; i <= 1000; i++)
  {
    printf("%d,", fast_pow(i, i, 7));

    if (i % 7 == 0)
      printf("\n");
  }

  return 0;

}

//以42为一组

1,4,6,4,3,1,0,

1,1,4,2,1,6,0,

1,2,5,1,5,1,0,

1,4,1,4,4,6,0,

1,1,3,2,6,1,0,

1,2,2,1,2,6,0,

1,4,6,4,3,1,0,

1,1,4,2,1,6,0,

1,2,5,1,5,1,0,

1,4,1,4,4,6,0,

1,1,3,2,6,1,0,

1,2,2,1,2,6,0,

1,4,6,4,3,1,0,

1,1,4,2,1,6,0,

1,2,5,1,5,1,0,

1,4,1,4,4,6,0,

1,1,3,2,6,1,0,

1,2,2,1,2,6,0,

1,4,6,4,3,1,0,

1,1,4,2,1,6,0,

1,2,5,1,5,1,0,

1,4,1,4,4,6,0,

1,1,3,2,6,1,0,

1,2,2,1,2,6,0,

1,4,6,4,3,1,0,

1,1,4,2,1,6,0,

1,2,5,1,5,1,0,

1,4,1,4,4,6,0,

1,1,3,2,6,1,0,

1,2,2,1,2,6,0,

1,4,6,4,3,1,0,

1,1,4,2,1,6,0,

1,2,5,1,5,1,0,

1,4,1,4,4,6,0,

1,1,3,2,6,1,0,

1,2,2,1,2,6,0,

1,4,6,4,3,1,0,

1,1,4,2,1,6,0,

1,2,5,1,5,1,0,

1,4,1,4,4,6,0,

1,1,3,2,6,1,0,

1,2,2,1,2,6,0,

1,4,6,4,3,1,0,

1,1,4,2,1,6,0,

1,2,5,1,5,1,0,

1,4,1,4,4,6,0,

1,1,3,2,6,1,0,

1,2,2,1,2,6,0,

2.然后打表求出[1,42]区间每个数n的(n^n)%7,再求a数组的前缀和b数组,

sum表示一个循环节所贡献的天数,即sum=(1^1+2^2+3^3+......+41^41+41^42)%7=6;

对于每一个样例n,直接计算即可

AC代码:C++

#include<bits/stdc++.h>

using namespace std;

chars[10][10] = {"Saturday", "Sunday", "Monday", "Tuesday", "Wednesday", "Thursday", "Friday"};

int fast_pow(int a, int n, int mod) //快速幂取模
{
    int ret = 1;

    while (n) {
        if (n & 1)
            ret = ret * a % mod;
        a = a * a % mod;
        n >>= 1;
    }

    return ret;
}

int a[50];//a[n]表示(n^n)%7
int b[50];//b[n]表示a[1]+a[2]+....+a[n]

int main()
{
    ios::sync_with_stdio(0);
    b[0] = 0;

    for (int i = 1; i <= 42; i++) //循环节为42
    {
        a[i] = fast_pow(i, i, 7);
        b[i] = b[i - 1] + a[i];
    }

    int t;

    cin >> t;

    while (t--) {
        int n;
        cin >> n;
        int sum = b[42] % 7; //一个循环节贡献的天数
        int num = n / 42; //循环节的个数
        int ans = (sum * num % 7 + b[n % 42] % 7) % 7;
        printf("%s\n", s[ans]);
    }

    return 0;

}

另一种计算sum的方法:

#include<bits/stdc++.h>
using namespace std;

chars[10][10] = {"Saturday", "Sunday", "Monday", "Tuesday", "Wednesday", "Thursday", "Friday"};

int fast_pow(int a, int n, int mod) //快速幂取模
{
    int ret = 1;

    while (n) {
        if (n & 1)
            ret = ret * a % mod;
        a = a * a % mod;
        n >>= 1;
    }

    return ret;
}

int a[50];//a[n]表示(n^n)%7
int b[50];//b[n]表示a[1]+a[2]+....+a[n]

int main()
{
    ios::sync_with_stdio(0);
    b[0] = 0;
    int sum = 0;

    for (int i = 1; i <= 42; i++) //循环节为42
    {
        a[i] = fast_pow(i, i, 7);
        b[i] = b[i - 1] + a[i];
        sum = (sum % 7 + a[i] % 7) % 7; //重点理解
    }

    int t;
    cin >> t;

    while (t--) {
        int n;
        cin >> n;
        int ans = (sum * (n / 42) % 7 + b[n % 42] % 7) % 7;
        printf("%s\n", s[ans]);
    }

    return 0;
}

原文发布于微信公众号 - ACM算法日常(acm-clan)

原文发表时间:2018-05-15

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏PPV课数据科学社区

用 Python 做文本挖掘的流程

作者:肖智博 来源:https://zhuanlan.zhihu.com/p/19630762 点击阅读原文可进入超链接。 收集数据 数据集。如果是已经被人做...

47380
来自专栏架构说

leetcode打家劫舍问题

https://leetcode-cn.com/problems/house-robber/description/

19720
来自专栏数据派THU

一文盘点三大顶级Python库(附代码)

Python在许多方面有着强大的吸引力 - 例如效率、代码可读性和速度方面,也正因为如此,对于希望提升应用程序功能的数据科学家和机器学习专家来说,Python通...

21340
来自专栏HansBug's Lab

洛谷讲课手稿

Hello大家好,我是洛谷的HansBug。首先自我介绍下,我现在在北京航空航天大学,计算机科学与技术专业读大二,我参加过2013-2015年的提高组NOIP和...

32740
来自专栏素质云笔记

R︱Yandex的梯度提升CatBoost 算法(官方述:超越XGBoost/lightGBM/h2o)

俄罗斯搜索巨头 Yandex 昨日宣布开源 CatBoost ,这是一种支持类别特征,基于梯度提升决策树的机器学习方法。 CatBoost 是由 Yand...

58790
来自专栏数据魔术师

运筹学教学|修正单纯形法(revised simplex algorithm)代码分享及详细注释

欢声笑语中,小编学会了单纯形法,心里还有点小傲骄!!准备晚上去PUBG里面潇洒一把~ ? 然而,老板突然来电话说,单纯形法有升级的版本!需要我赶紧准备一份代码。...

90870
来自专栏斑斓

MongoDB的数据建模

MongoDB是一种面向Document的NoSQL数据库,如果我们还是按照RDB的方式来思考MongoDB的数据建模,则不能有效地利用MongoDB的优势;然...

35660
来自专栏小樱的经验随笔

1022: [SHOI2008]小约翰的游戏John【Nim博弈,新生必做的水题】

1022: [SHOI2008]小约翰的游戏John Time Limit: 1 Sec  Memory Limit: 162 MB Submit: 2709 ...

33180
来自专栏程序人生

谈谈状态机

题记:上周做 BBL 里讲了我们 Tubi TV 内部做 DSL 的一些简单实践,大家反馈不错。有同事建议我给大家先补补 FSM,之后再进阶 CFG,可能会更顺...

38370
来自专栏好好学java的技术栈

“365算法每日学计划”:03打卡-贪心算法

自从开始做公众号开始,就一直在思考,怎么把算法的训练做好,因为思海同学在算法这方面的掌握确实还不够。因此,我现在想做一个“365算法每日学计划”。

24620

扫码关注云+社区

领取腾讯云代金券