ARC064 F Rotated Palindromes(1000)

部分問題への分割

基本にのっとって問題の分割をすると、再帰的な問題だと気づく

まさか解法が降ってくるとは思わなかった

1. #include<iostream>
2. #include<algorithm>
3. #include<vector>
4. #include<queue>
5. #define lol(i,n) for(int i=0;i<n;i++)
6. #define mod 1000000007
7. typedef long long ll;
8. using namespace std;
10. ll Pmod(ll n,ll k){
11. ll r=k,ret=1;
12. while(true){
13. if(n==0)break;
14. if(n%2==1){
15. ret=ret*r%mod;
16. }
17. n/=2;
18. r=r*r%mod;
19. }
20. return ret;
21. }
23. vector<pair<ll,ll> > v;
24. int main(){
25. ll n,k;
26. cin>>n>>k;
27. for(ll i=1;i*i<=n;i++){
28. if(n%i==0){
29. v.push_back(make_pair(i,-1));
30. if(i!=n/i)v.push_back(make_pair(n/i,-1));
31. }
32. }
33. sort(v.begin(),v.end());
34. ll ans[2]={0,0};
35. for(int i=0;i<v.size();i++){
36. ll x=v[i].first;
37. ll tmp=Pmod((x+1)/2,k);
38. for(int j=0;j<i;j++){
39. if(x%v[j].first==0){
40. tmp=(mod+tmp-v[j].second)%mod;
41. }
42. }
43. v[i].second=tmp;
44. ans[x%2]+=tmp*x%(mod*(ll)10);
45. }
46. //cout<<ans[0]<<" "<<ans[1]<<endl;
47. cout<<(ans[0]/2+ans[1])%mod<<endl;
48. return 0;
49. }

後で割る時は、modで抑えるといけないのでmodを5倍くらいにしとく