Euler theorem

Posted on | In , ,

题目链接

题意

计算$a%b$的不同可能结果，已知$a$。

思路

数字$a$的余数一定比$b$小，所以可能结果只有$a$大小一半的规模，且必有两个可能结果$0$和$a$，在$1$到$a-1$这$n-1$个数字中，只有$1$到可以作为余数。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#ifndef ONLINE_JUDGE
#define dbg(x...) do{cout << "\033[33;1m" << #x << "->" ; err(x);} while (0)
void err(){cout << "\033[39;0m" << endl;}
template<template<typename...> class T, typename t, typename... A>
void err(T<t> a, A... x){for (auto v: a) cout << v << ' '; err(x...);}
template<typename T, typename... A>
void err(T a, A... x){cout << a << ' '; err(x...);}
#else
#define dbg(...)
#endif
#define inf 1ll << 50
int main(){
	int t;
	scanf("%d",&t);
	while(t--){
		int n;
		scanf("%d",&n);
		printf("%d\n",(n-1)/2+2);
	}
}
0%