Rahul, the geek boy of his class, doesn't like doing things the conventional way. He's just learned polynomials in class, and wants to prove a point to his friend Sandhya. But Sandhya is sitting in the first bench, so Ram decides to write what he wants to convey on a chit and pass it through the guys sitting in front of him. The guys in between try to read it, but do not understand. Sadly, nor does Sandhya. Can you help him out?
次の多項式も与えられる
p = x406 + x405 + x402 + x399 + x397 + x391 + x390 + x387 + x386 + x378 + x374 + x372 + x371 + x369 + x367 + x364 + x360 + x358 + x357 + x352 + x350 + x345 + x344 + x341 + x336 + x335 + x334 + x333 + x331 + x330 + x329 + x328 + x327 + x324 + x322 + x320 + x314 + x311 + x308 + x307 + x303 + x300 + x299 + x296 + x295 + x290 + x289 + x287 + x279 + x271 + x266 + x264 + x262 + x260 + x257 + x256 + x252 + x249 + x248 + x246 + x243 + x239 + x238 + x236 + x233 + x230 + x227 + x225 + x223 + x222 + x220 + x218 + x216 + x215 + x209 + x208 + x207 + x204 + x202 + x199 + x190 + x189 + x185 + x184 + x180 + x177 + x176 + x175 + x172 + x167 + x166 + x162 + x160 + x159 + x155 + x154 + x149 + x147 + x143 + x137 + x135 + x131 + x129 + x126 + x124 + x122 + x116 + x110 + x108 + x105 + x104 + x100 + x99 + x97 + x94 + x93 + x90 + x88 + x87 + x86 + x85 + x83 + x75 + x73 + x69 + x63 + x62 + x57 + x54 + x51 + x44 + x41 + x38 + x37 + x36 + x34 + x29 + x28 + x26 + x25 + x21 + x20 + x19 + x16 + x15 + x14 + x13 + x6 + x5 + x2
q = x399 + x398 + x396 + x393 + x392 + x391 + x388 + x386 + x384 + x381 + x377 + x376 + x368 + x364 + x360 + x355 + x354 + x353 + x352 + x348 + x346 + x345 + x344 + x343 + x335 + x334 + x329 + x326 + x325 + x321 + x318 + x317 + x315 + x314 + x311 + x307 + x306 + x304 + x300 + x296 + x293 + x291 + x282 + x277 + x270 + x263 + x261 + x260 + x256 + x254 + x253 + x252 + x251 + x248 + x245 + x242 + x241 + x239 + x238 + x236 + x232 + x226 + x225 + x222 + x220 + x219 + x214 + x209 + x208 + x207 + x206 + x202 + x200 + x196 + x191 + x190 + x186 + x181 + x180 + x178 + x177 + x169 + x168 + x165 + x164 + x163 + x162 + x161 + x159 + x157 + x156 + x151 + x149 + x148 + x147 + x146 + x144 + x141 + x140 + x138 + x137 + x136 + x134 + x133 + x132 + x130 + x129 + x128 + x126 + x123 + x121 + x113 + x109 + x103 + x101 + x100 + x95 + x93 + x91 + x85 + x84 + x81 + x74 + x73 + x71 + x68 + x67 + x54 + x52 + x51 + x50 + x48 + x46 + x45 + x43 + x39 + x35 + x32 + x31 + x30 + x29 + x21 + x15 + x14 + x9 + x8 + x5 + x4 + x2 + 1
r = x404 + x402 + x396 + x389 + x387 + x386 + x384 + x382 + x376 + x373 + x367 + x366 + x365 + x362 + x361 + x358 + x356 + x355 + x354 + x353 + x352 + x349 + x348 + x347 + x345 + x343 + x340 + x334 + x332 + x331 + x328 + x327 + x326 + x322 + x317 + x316 + x314 + x313 + x312 + x310 + x309 + x308 + x305 + x304 + x303 + x301 + x300 + x299 + x296 + x295 + x292 + x291 + x290 + x288 + x287 + x286 + x285 + x283 + x279 + x278 + x274 + x271 + x269 + x268 + x266 + x265 + x263 + x261 + x260 + x259 + x258 + x256 + x254 + x252 + x251 + x250 + x249 + x244 + x243 + x242 + x237 + x236 + x228 + x225 + x224 + x223 + x222 + x221 + x215 + x214 + x213 + x212 + x205 + x201 + x200 + x199 + x197 + x193 + x192 + x191 + x190 + x189 + x188 + x187 + x182 + x180 + x175 + x174 + x173 + x167 + x166 + x163 + x158 + x156 + x155 + x153 + x151 + x150 + x149 + x143 + x142 + x140 + x139 + x136 + x135 + x133 + x129 + x126 + x125 + x123 + x121 + x118 + x117 + x116 + x115 + x113 + x110 + x106 + x105 + x104 + x103 + x102 + x98 + x95 + x92 + x89 + x87 + x85 + x81 + x80 + x77 + x76 + x75 + x74 + x71 + x70 + x67 + x66 + x64 + x63 + x60 + x59 + x58 + x56 + x54 + x53 + x48 + x44 + x41 + x39 + x38 + x35 + x34 + x31 + x29 + x28 + x27 + x22 + x21 + x20 + x17 + x14 + x12 + x11 + x10 + x9 + x6 + x4 + x3 + x + 1
なんかN乗になっているところの回数を数えてmod2をとってバイナリ列にすると解けるらしい。
from Crypto.Util.number import long_to_bytes p = [ "406", "405", "402", "399", ... "13", "6", "5", "2", ] q = [ "399", "398", ... "2", "0", ] r = [ "404", "402", ... "0", ] binstr = "" for i in range(406, -1, -1): c = str(i) cnt = 0 if c in p: cnt += 1 if c in q: cnt += 1 if c in r: cnt += 1 binstr += str(cnt % 2) print(long_to_bytes(int(binstr, 2)))
へー以外の感想がない
