C-最大模数
题目描述
一次周六新生训练后,一个师妹来找JAJA_Xin。
师妹:“师兄,为什么今天我对面那个师兄那么冷漠。”
JAJA_Xin:“噢你居然还不认识大名鼎鼎的魏队,正常啦,魏队很傲的,因为你们太菜,所以你懂的。”
师妹:“那怎么才能让那个师兄觉得我不菜,你可以帮我去问问吗?”
乐于助人的JAJA_Xin怎么可能拒绝师妹呢,跑去问魏队。
魏队:“简单啊,我出一道题,能做出来就不算很菜了,就出一道数学题吧,简单一点,让他们可以做。”
Ra=[(a−1)n+(a+1)n](mod $ a^2$$)$$ ,(n>0)例如当a=4, n=2时,Ra=32 +52 =34$,而34mod16=2,故Ra=2。由于n可以是任意大于0的正整数,所以存在很多Ra的解,找到任意一个Ra就算做出来这道题。例如,当a=4的时候,Ra的取值可以是2或者是8。
“你怎么这么有空还管闲事,不赶紧去补题吗…”,JAJA_Xin被魏队一顿说了之后闷闷不乐,不小心就把原题意记成了要找到最大的Ra才能算做出来这道题,并把修改的题意后和师妹说了,这可难到他们了。例如,当a=4的时候,$R_{a_{max}}=8$。
输入描述
多测试用例,用例不超过10000个。
每个用例有一行数据,一个整数a(3≤a≤1000000)。
输出描述
对于每个用例输出一行,$R_{a_{max}}$。
示例1
输入
4
7
输出
8
42
思路
先找一下规律,取n=1,2,3,4,5,由二项式展开:
n=1:(a−1)+(a+1)=2a
n=2:(a−1)2+(a+1)2=2a2+2
n=3:(a−1)3+(a+1)3=2a3+6a
n=4:(a−1)4+(a+1)4=2a4+12a2+2
n=5:(a−1)5+(a+1)5=2a5+20a3+10a
$mod $ a2后,有:
n=1:2a
n=2:2
n=3:6a
n=4:2
n=5:10a
找到规律,若n为偶数,结果为2 mod a2;若n为奇数,结果为2na mod a2 ,由于n可以取任意值,所以可以认为2na mod a2>2,问题转化为求2na mod a2的最大值。
初步判断,知道2na=a2 时n的取值,把n−1代入上式,结果就是最大值。
进一步,通过化简2na=a2 ,可以得到 n=2a。 故需要再考虑a的奇偶性:
①当 a 为奇数
由于 2na=2⋅2a⋅a<a2 , 所以不需要取n−1,此时Ra就是最大模数了。
最大模数就是$ 2·\frac{a}{2}· a=a^2-a$。
②当 a 为偶数
由于 2na=2⋅2a⋅a<a2 , 此时Ra=0,所以取n−1,即n=2a−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; }
|
输入描述
第一行一个整数t代表有t组测试用例,0≤t≤100。
接下来t行,输入一个仅包含’Z’,'Q’和’U’三种字符的字符串s。($ 0<|s|≤100000,|s|为字符串s$的长度)。
输出描述
每行一个整数表示代码中ans的值。
示例1
输入
2
ZQUZQU
ZQUZQUZQU
输出
4
10
备注
TLE了吧【奸笑】,师兄太坏了,不行,这样不好。这道主要锻炼你快速读懂别人代码的能力,好好理解这段代码,想想怎么优化吧。
思路
要求有多少个"ZQU"这样的子序列,是一个排列组合问题。假设共有q个’Q’,如果第i个’Q’前面有z个’Z’,后面有u个’U’,那么以第i个’Q’为中心组成的子序列"ZQU"就有uz个。
于是,我们只需要分别正序和逆序遍历字符串,求出每一个’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; }
|