题目链接
Training #10
F
思路
这道题就是打表找规律，然后发现满足的式子是f[1]=4,f[2]=14,f[n]=4*f[n-1]-f[n-2];
得到这个式子之后考虑大数的问题，看到大数直接上java就好了。
代码实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
| import java.math.BigInteger;
import java.util.*;
public class Main {
public static void main(String[] args) {
int T;
Scanner in = new Scanner(System.in);
T=in.nextInt();
BigInteger[] num = new BigInteger[150];
num[0]=BigInteger.valueOf(4);
num[1]=BigInteger.valueOf(4);
num[2]=BigInteger.valueOf(14);
for(int i=3;i<150;i++)
{
num[i]=num[i-1].multiply(BigInteger.valueOf(4));
num[i]=num[i].subtract(num[i-2]);
}
while(T-->0)
{
BigInteger n = in.nextBigInteger();
for(int i=0;i<150;i++)
{
if(n.compareTo(num[i])!=1)
{
System.out.println(num[i]);
break;
}
}
}
}
}
|
E
题目链接
(模板)欧拉筛
思路
其实这道题是个思维题，当n>p的时候，后面的取余全为0，所以只需要考虑1e5之内的就够了。
代码实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
| #include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 1e5+10;
int prime[N],cnt;
bool vis[N];
void init()
{
vis[1]=true;
for(int i=2;i<N;i++)
{
if(!vis[i])prime[cnt++]=i;
for(int j=0;j<cnt&&i*prime[j]<N;j++)
{
vis[i*prime[j]]=1;
if(i%prime[j]==0)break;
}
}
}
int main()
{
init();
int t;
scanf("%d",&t);
while(t--)
{
ll n,p,sum=1,ans=0;
cin>>n>>p;
for(int i=1;i<=min(n,p);i++)
{
sum=(sum*i)%p;
if(!vis[i])ans=(ans+sum)%p;
}
cout<<ans<<endl;
}
}
|