2018年2/3月月赛 Day2 被7整除 题解

2018年2/3月月赛 Day2 被7整除 题解

题目描述

输出从1~n有多少个整数满足2^n-n^2能被7整除。

输入输出格式

输入格式

一行，包含一个整数n。

输出格式

一行，包含一个整数x，表示从1~n有x个整数满足2^n-n^2能被7整除。

输入输出样例

输入样例#1：

2

输出样例#1：

1

输入样例#2：

4

输出样例#2：

2

说明

对于100%的数据，1<=n<=1000000。

定性为数论题。

通过打表可发现有周期为21的规律。

只能打表自行找规律，没有别种办法。

找不出规律也可暴力，不过会超时。

代码：

#include<iostream>
#include<cstdio>
using namespace std;
#define ll long long
int main()
{
  int num[30]={0,0,1,1,2,3,4,4,4,4,5,5,5,5,5,6,6,6,6,6,6,6};
  int n;
  cin>>n;
  int k=n/21,q=n%21;
  cout<<k*6+num[q];
  return 0;
}