湖南网站建设深圳电子网络推广查询

题目描述

小蓝发现，对于一个正整数 nn 和一个小于 nn 的正整数 vv，将 vv 平方后对 nn 取余可能小于 nn 的一半，也可能大于等于 nn 的一半。

请问，在 11 到 n−1n−1 中, 有多少个数平方后除以 nn 的余数小于 nn 的一半。

例如，当 n=4n=4 时，1,2,31,2,3 的平方除以 44 的余数都小于 44 的一半。

又如，当 n=5n=5 时, 11，44 的平方除以 55 的余数都是 11，小于 55 的一半。而 22，33 的平方除以 55 的余数都是 44, 大于等于 55 的一半。

输入格式

输入一行包含一个整数 nn 。

输出格式

输出一个整数，表示满足条件的数的数量。

输入样例

5

输出样例

2

代码示例
 

import java.util.*;
public class Main {public static void main(String[] args) {Scanner scan = new Scanner(System.in);int n = scan.nextInt();int ans = 0;for(int i = 1; i < n ; i++) {long res = i*i;res%=n;if(res*2<n)ans++;}System.out.print(ans);}
}