昨天做题目一个BUG死活调不出来，事后发现时取模的优化用错了……就是所谓的使用位运算优化取模，而这个优化时我很早以前从某个博客上看来的。

出处

示例：

//判断a是否能被b整除
//正常写法
bool flag=a%b;

//"优化"写法
bool flag=a&(b-1);

平时一直没有发现，因为用的都是较大的数据这样做，这次是数据较小暴雷了，于是我开始好奇它的正确率。

写了个暴力枚举进行验证，对于任意满足 $1<=i , j<=10^{n}$ 的 $i ,j$ , 其正确率是多少。

• $n= 1$ $\qquad$ $68.00 \%$
• $n= 2$ $\qquad$ $82.93 \%$
• $n= 3$ $\qquad$ $94.13 \%$
• $n= 4$ $\qquad$ $97.01 \%$
• $n= 5$ $\qquad$ $98.93 \%$
• $n= 6$ $\qquad$ $99.65 \%$

用的是 $O(n^{2})$ 算法， 6的时候就已经到万亿了……再乘个100破笔记本实在撑不住了。 但是数据已经能很好的说明，这样子“优化”居然是有其合理性的，就是很看人品……

下面是巨丑的代码：

#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<cstdio>
using namespace std;

int main()
{
	long long times = 0, limit = 1;
	int a; scanf("%d", &a);
	for (int i = 1; i <= a;i++)
	{
		limit *= 10;
	}
	//freopen("test.out", "w", stdout);
	for (long long i = 1; i <= limit;i++)
	{
		for (long long j = 1; j <= limit; j++)
		{
			long long qumo = i % j;
			long long wys = i & (j -1);
			bool xiangtong = ((qumo != 0) == (wys != 0));
			if (xiangtong)
			{
				//printf("相同  ");
			}
			else
			{
				//printf("不相同  "); 
				times++;
			}
			//printf("取模: %d    位运算:%d   i=%d   j=%d   \n", qumo,wys,i,j);
		}
	}
	long long ans = limit * limit - times;
	printf("%lld.%lld", ans*100 / (limit * limit),(ans*10000/(limit*limit))%100);
	//printf("%lld ", times);
}