南京理工大学C題

まず、暴力は耐えられないに違いないと分析することができます.a、bの範囲は10の15次レベルなので、この問題は他の方法を探す必要があります.それは反発原理です.
1−bにおけるnと非互質の個数を求め,次いで1−(a−1)におけるnと非互質の個数を減算し,最終的に得られた結果が問題に必要な結果である.
では、どのようにして大きな数mとnが互いに質を持たない個数を迅速に求めることができますか.方法は、2,3,5のようなnの質因子を求めることです.
1-mにはm/2個の数とnに公因子2があり、m/3個の数とnに公因子3があり、m/5個の数とnに公因子5がある...しかし,m/2+m/3+m/5を最後にnと相互作用しない個数として簡単には使用できない.
10のように、m/2にもm/5にも計算するので、反発原理式として用いる必要があるのは、n/2+n/3+n/5-n/(2*3)-n/(2*5)-n/(3*5)+n/(2*3*5)+n/(2*3*5)である.
これで正しいことを保証します!!

#include <cstdio>
#include <cstring>
#include <string>
#include <iostream>
#include <algorithm>
#include <stack>
#include <queue>
#include <map>
#include <vector>
#include <cmath>
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
using namespace std;
const int maxx = 10000005;
const int maxn = 55555;
typedef long long int ll;
ll a[maxn], que[maxn], prime[maxx / 10];
bool visit[maxx];
int n;


void getPrime()
{
	int i, j;
	memset(prime, 0, sizeof(prime));
	for (i = 0; i<maxx; i++)
		visit[i] = true;
	visit[0] = visit[1] = false;
	for (i = 2; i<maxx; i++)
	{
		if (visit[i])
		{
			prime[++prime[0]] = i;
			for (j = i; j<maxx; j += i)
				visit[j] = false;                        //   ，      ，       
		}
	}
}
ll ans(ll nn)                //     1-n  n      
{
	ll t = n;
	int i, j, k = 0;
	for (i = 1; prime[i] * prime[i] <= t; i++)
	{
		if (t%prime[i] == 0)
		{
			a[k++] = prime[i];
		}
		while (t%prime[i] == 0)                    //       ，     
		{
			t /= prime[i];
		}
	}
	if (t != 1)
		a[k++] = t;
													 //a     n      
	que[0] = -1;
	t = n;
	int kk = 1;
	for (i = 0; i<k; i++)							 //que             ,         ，            
	{
		t = kk;                                       //              ，                
		for (int w = 0; w <t; w++)
		{
			que[kk++] = a[i] * (-1)*que[w];
		}
	}
	ll res = 0;
	for (i = 1; i<kk; i++)
	{
		res += nn / que[i];
	}
	return res;
}
int main(void)
{
	//freopen("in.txt", "r", stdin);
	int T;
	ll a, b;
	getPrime();
	scanf("%d", &T);
	while (T--)
	{
		scanf("%lld%lld%lld", &a, &b, &n);
		printf("%lld
", b - ans(b) - (a - 1 - ans(a - 1)));                     //        ，           ，      
	}
	return 0;
}