牛客月賽12-華華給月月出題-(線性篩)

C

題意：

就是給你n，讓你求出i從1到n，i的n次方的異或和。

思考：

如果直接對1到n每次求ksm，肯定會逾時。其實這種題隻要範圍比較大，一般都是線性篩，要麼是O(nlogn)這個數會出現多少次:many sum。要麼就是O(n)的篩法:有毒的玻璃球。要麼就是歐拉曬中間取維護一些東西。這題用到了一個性質就是任何一個數都可以表示為一個質數和另一個數的乘積，是以每次求ksm隻會對質數求罷了，别的都是直接曬出來。

代碼：

歐拉曬維護一些值：

int T,n,m,k;
ll res[N];
bool st[N];
int pri[N],cnt;

ll ksm(ll a,ll b)
{
	ll sum = 1;
	while(b)
	{
		if(b&1) sum = sum*a%mod;
		b >>= 1;
		a = a*a%mod;
	}
	return sum;
}

void init(int x)
{
	res[1] = 1;
	for(int i=2;i<=x;i++)
	{
		if(!st[i])
		{
			pri[++cnt] = i;
			res[i] = ksm(i,n)%mod;
		}
		for(int j=1;pri[j]*i<=x;j++)
		{
			st[pri[j]*i] = 1;
			res[pri[j]*i] = res[i]*res[pri[j]]%mod; //i*pri[j]可以直接被表示出來，這裡res[i]和res[pri[j]]的值肯定已經曬出來過了
			if(i%pri[j]==0) break;
		}
	}
}

signed main()
{
	IOS;
	cin>>n;
	init(n);
	ll anw = 0;
	for(int i=1;i<=n;i++) anw ^= res[i];
	cout<<anw;
	return 0;
}

many sum代碼：

int T,n,m,k;
int va[N];
int sum[N];

void init()
{
	for(int i=1;i<=n;i++)
	{
		for(int j=i;j<=n;j+=i)
		sum[j] += va[i];
	}	
}

signed main()
{
	IOS;
	cin>>n>>va[1]>>m;
	for(int i=2;i<=n;i++) va[i] = (va[i-1]+7*i)%m;
	init();
	int ans = 0;
	for(int i=1;i<=n;i++) ans ^= sum[i];
	cout<<ans;
	return 0;
}

有毒的玻璃球代碼：

int T,n,m,k;
int va[N];
int sum[N];
 
int ksm(int a,int b)
{
    int sum = 1;
    while(b)
    {
        if(b&1) sum = sum*a%mod;
        a = a*a%mod;
        b >>= 1;
    }
    return sum;
}
 
signed main()
{
    IOS;
    cin>>n>>m;
    int ans = 0;
    for(int i=1;i<=n;i++)
    {
        int sum = n/i;
        ans = (ans+sum*ksm(i,m)%mod)%mod;
    }
    cout<<ans;
    return 0;
}
           

總結：

多多積累經驗呀，就和以前做過的題或者學過的算法聯合起來。