C-最大模数

题目描述

一次周六新生训练后，一个师妹来找JAJA_Xin。
师妹：“师兄，为什么今天我对面那个师兄那么冷漠。”
JAJA_Xin：“噢你居然还不认识大名鼎鼎的魏队，正常啦，魏队很傲的，因为你们太菜，所以你懂的。”
师妹：“那怎么才能让那个师兄觉得我不菜，你可以帮我去问问吗？”
乐于助人的JAJA_Xin怎么可能拒绝师妹呢，跑去问魏队。
魏队：“简单啊，我出一道题，能做出来就不算很菜了，就出一道数学题吧，简单一点，让他们可以做。”
Ra=[(a−1)n+(a+1)n]R_a = [ (a−1)^n + (a+1)^n ]((modmod $ a^2$$)$$ ,(n>0)例如当 例如当a=4, n=2时，时，Ra=32 +52 =34$，而34mod16=234mod16 =2,故Ra=2R_a=2。由于n可以是任意大于0的正整数，所以存在很多RaRa的解，找到任意一个Ra就算做出来这道题。例如，当a=4a=4的时候，RaRa的取值可以是22或者是88。
“你怎么这么有空还管闲事，不赶紧去补题吗…”，JAJA_Xin被魏队一顿说了之后闷闷不乐，不小心就把原题意记成了要找到最大的RaR_a才能算做出来这道题，并把修改的题意后和师妹说了，这可难到他们了。例如，当a=4a=4的时候，$R_{a_{max}}=8$。

输入描述

多测试用例，用例不超过1000010000个。
每个用例有一行数据，一个整数a(3≤a≤1000000)a (3≤a≤1000000)。

输出描述

对于每个用例输出一行，$R_{a_{max}}$。

示例1

输入
4
7
输出
8
42

思路

先找一下规律，取n=1,2,3,4,5n=1,2,3,4,5，由二项式展开：
n=1:(a−1)+(a+1)=2an=1:(a-1)+(a+1)=2a
n=2:(a−1)2+(a+1)2=2a2+2n=2:(a-1)^2+(a+1)^2=2a^2+2
n=3:(a−1)3+(a+1)3=2a3+6an=3:(a-1)^3+(a+1)^3=2a^3+6a
n=4:(a−1)4+(a+1)4=2a4+12a2+2n=4:(a-1)^4+(a+1)^4=2a^4+12a^2+2
n=5:(a−1)5+(a+1)5=2a5+20a3+10an=5:(a-1)^5+(a+1)^5=2a^5+20a^3+10a
$mod $ a2a^2后，有：
n=1:2an=1:2a
n=2:2n=2: 2
n=3:6an=3:6a
n=4:2n=4:2
n=5:10an=5:10a
找到规律，若nn为偶数，结果为22 modmod a2a^2；若nn为奇数，结果为2na2na modmod a2a^2 ，由于nn可以取任意值，所以可以认为2na2na modmod a2>2a^2>2，问题转化为求2na2na modmod a2a^2的最大值。
初步判断，知道2na=a22na=a^2 时nn的取值，把n−1n-1代入上式，结果就是最大值。
进一步，通过化简2na=a22na = a^2 ，可以得到 n=a2n= \frac{a}{2}。 故需要再考虑a的奇偶性：
①当 a 为奇数
由于 2na=2⋅a2⋅a<a22na = 2·\frac{a}{2}· a < a^2 , 所以不需要取n−1n-1，此时RaR_a就是最大模数了。
最大模数就是$ 2·\frac{a}{2}· a=a^2-a$。
②当 a 为偶数
由于 2na=2⋅a2⋅a<a22na = 2·\frac{a}{2}· a < a^2 , 此时Ra=0R_a = 0，所以取n−1n-1，即n=a2−1n = \frac{a}{2}-1。
最大模数就是$ 2 ·a · ( \frac{a}{2} - 1 ) = a^2 - 2a$ 。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include <iostream>
#define ll long long
using namespace std;
ll solve(ll a)
{
    if(a&1) return a*a-a;
    else return a*a-2*a;
}
int main()
{
    ios::sync_with_stdio(false);    
    cin.tie(0);
    cout.tie(0);   
    ll a;
    while(cin>>a) cout<<solve(a)<<endl;
    return 0;
}

J-试试划水

题目描述

师兄猜你看的第一道题是这道哈哈哈。没错，师兄给你送福利了，这道题你只需要呆萌呆萌的把下面的代码交上去就行了，师兄是好人【坏笑】。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include<stdio.h>  
#include<string.h>  
char ch[100000+5];  
int main()  
{    
    int t;    
    scanf("%d",&t);  
    while(t--) {    
        int len,ans=0;       
        scanf("%s",ch);    
        len=strlen(ch);    
        for(int i=0;i<len;i++)    
           for(int j=i+1;j<len;j++)    
               for(int k=j+1;k<len;k++)        
                  if(ch[i]=='Z'&&ch[j]=='Q'&&ch[k]=='U')            
                      ans++;      
         printf("%d\n",ans);
    
    }    
    return 0;
}

输入描述

第一行一个整数tt代表有tt组测试用例，0≤t≤1000≤t≤100。
接下来tt行，输入一个仅包含’Z’,'Q’和’U’三种字符的字符串ss。($ 0<|s|≤100000，，|s|为字符串为字符串s$的长度)。

输出描述

每行一个整数表示代码中ans的值。

示例1

输入
2
ZQUZQU
ZQUZQUZQU
输出
4
10

备注

TLE了吧【奸笑】，师兄太坏了，不行，这样不好。这道主要锻炼你快速读懂别人代码的能力，好好理解这段代码，想想怎么优化吧。

思路

要求有多少个"ZQU"这样的子序列，是一个排列组合问题。假设共有qq个’Q’，如果第ii个’Q’前面有zz个’Z’，后面有uu个’U’，那么以第ii个’Q’为中心组成的子序列"ZQU"就有uzuz个。
于是，我们只需要分别正序和逆序遍历字符串，求出每一个’Q’的前缀’Z’的个数和后缀’U’的个数。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
#include<iostream>
#include<string>
using namespace std;
void solve()
{
	const int N=100010;
	string s;
	cin>>s;
	int l=s.size()-1;
	int z=0,q=0,u=0;
	long long prefix[N],suffix[N];
	int i;
	for(i=0;i<=l;i++)//统计前缀
	{
		if(s[i]=='Z') z++;
		else if(s[i]=='Q') prefix[++q]=z;
	}
	int p=q;
	for(i=l;i>=0;i--)//统计后缀
	{
		if(s[i]=='U') u++;
		else if(s[i]=='Q') suffix[p--]=u;
	}
	long long ans=0;
	for(i=1;i<=q;i++)
	{
		ans+=prefix[i]*suffix[i];
	}
	cout<<ans<<endl;
}
int main()
{
	ios::sync_with_stdio(false);
	int t;
	cin>>t;
	while(t--) solve();
	return 0;
}